I'm writing a search algorithm in C++, and one of the things I need to do is have a few if statements that check cells above, below, left of, and right of.
Each time a cell is found to be open and added to the stack, I want it added to a list of cells already checked.
I want to be able to say in the if statement if(thisCell is not in checkedCells)
.
Any simple ideas?
We can use the in-built python List method, count(), to check if the passed element exists in the List. If the passed element exists in the List, the count() method will show the number of times it occurs in the entire list. If it is a non-zero positive number, it means an element exists in the List.
Python Find String in List using count() We can also use count() function to get the number of occurrences of a string in the list. If its output is 0, then it means that string is not present in the list. l1 = ['A', 'B', 'C', 'D', 'A', 'A', 'C'] s = 'A' count = l1.
For this purpose it's better to use the std::set
container, because it provides you with the ability to search for items faster than a list. Then you can write:
std::set<itemType> myset;
...
if (myset.find(item) != myset.end()) {
// item is found
}
A larger example can be found by googling. For example, here.
If the number of items are in the hundreds, you can use simple, sequential search. This algorithm is built-into C++ as the find()
function:
#include <algorithm> // for find()
typedef std::vector<Cell> CellList;
CellList checked_cells;
// .....
Cell cellToSearch;
if (is_in_checked_cells (cellToSearch, cells))
{
// .....
}
// Makes a sequential search using find().
static bool
is_in_checked_cells (const Cell &cell, const CellList &cells)
{
CellList::const_iterator end = cells.end ();
CellList::const_iterator item = std::find (cells.begin (), end, cell);
return (item != end);
}
Make sure Cell
has operator<
overridden.
If the list is very large, you may want to use binary search, which also comes bundled with C++:
#include <algorithm> // for sort() and binary_search()
CellList checked_cells;
// Make sure the cells are sorted.
checked_cells.sort (checked_cells.begin (), checked_cells.end ());
Cell cellToSearch;
if (is_in_checked_cells (cellToSearch, cells))
{
// .....
}
// Searches using binary_search().
static bool
is_in_checked_cells (const Cell &cell, const CellList &cells)
{
return std::binary_search (cells.begin (), cells.end (), cell);
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With