graph search algorithm - BFS OR Ad Hoc
At first I was confused by the problem description, and I thought that the sample output doesn't match the sample input. The problem wants to know that if you are standing in a cell occupied with digit '1', at most how many steps does it take to get to a cell (just one) occupied with digit 3.
So first I find the minimum distance from each '1' to each '3' and take the minimum of these values, then I just iterate through the minimum values I took for each '1' and print the maximum one.
To find the minimum distance from each '1' to each '3' you can run a BFS from that '1' and then pick the minimum of the distances from the '1', but I don't suggest to do that, because in grids BFS is used when you have some special adjacency for cells or you have some obstacles in the path between two cells, but here you can easily calculate the minimum distance between two cells.
the Distance from cell A to cell B = abs( A.x-B.x ) + abs( A.y-B.y )
This is true if you are allowed to move one cell up, down, left or right, but not diagonally.
#include
ReplyDelete#include
#include
#include
#include
#include
using namespace std;
char Field[1000][1000];
int main()
{
vector< pair >V;
vector< pair >VV;
int Size;
int Max;
int result;
int Min;
while(cin>>Size)
{
Min=-1;
Max=999999999;
for(int j=0;j>Field[j][i];
if(Field[j][i]=='1')
{
VV.push_back(make_pair(j,i));
}
else if(Field[j][i]=='3')
{
V.push_back(make_pair(j,i));
}
}
}
for(int ii=0;iiMin)
Min=Max;
}
cout<<Min<<endl;
}
return 0;
}