Booshi
BAN USERThis is a BFS solution.
This starts at starting oint of the country and visits all the node which is in the same country.
Starts a new country the next time it loops and finds a node which is not visited.
It searches from (0,0), visits only those nodes which are already not visited.
Searches top, bottom, left and right of the current node in the search.
# => current node
* => neighbour nodes
[1 * 1 1 1 1 1 1]
[* # * 1 1 0 0 0]
[0 * 0 0 0 0 0 0]
[0 0 0 1 1 1 1 1]
[0 1 1 1 1 1 1 1]
bool bound(int i, int j, int visited[][])
{
return (i >= 0 && j >= 0 && i <= horizontal && j <= vertical && visited[i][j]);
}
int countCountries(int input[][] int horizontal, int vertical)
{
int count = 0;
Queue BFSQueue; // Stores i, j in each node
bool visited[horizontal][vertical] = FALSE;
for(int i = 0; i < horizontal; i++)
{
for(int j = 0; j < vertical; j++)
{
if(!visited[i][j])
{
// Starting location - start at (0, 0)
BFSQueue.push(i, j);
int countryCode = input[i][j];
// Increment country count
count++;
// Search boundary for this country
Node thisNode;
while((thisNode = BFSQueue.pop()) != NULL)
{
if(input[thisNode.i][thisNode.j] != countryCode)
continue;
visited[thisNode.i][thisNode.j] = TRUE;
if(bound(thisNode.i - 1, thisNode.j, visited))
BFSQueue.push(thisNode.i - 1, thisNode.j);
if(bound(thisNode.i, thisNode.j - 1, visited))
BFSQueue.push(thisNode.i, thisNode.j - 1);
if(bound(thisNode.i + 1, thisNode.j, visited))
BFSQueue.push(thisNode.i + 1, thisNode.j);
if(bound(thisNode.i, thisNode.j + 1, visited))
BFSQueue.push(thisNode.i, thisNode.j + 1);
}
}
}
}
return count;
}
Question:
- Booshi January 25, 2015[1,1,1,0]
[1,1,0,0]
[0,0,0,1]
Look at this like a 2D MAP where the neighbouring country will have different codes.
The 3 countries are
1. Country with area defined by 1, * contains all other countries.
[1,1,1,*]
[1,1,*,*]
[*,*,*,*]
2. Country with area defined by 0, * contains all other countries.
[*,*,*,0]
[*,*,0,0]
[0,0,0,*]
3. Country with area defined by 1, * contains all other countries.
[*,*,*,*]
[*,*,*,*]
[*,*,*,1]
So in total 3 countries.