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.
Subscribe to:
Post Comments (Atom)
-
Link to the problem on Timus Online Judge First of all there are two kinds of input which the answer is zero, first if sum % 2 == 1 or se... -
Link to the problem on Timus Online Judge The problem statement is completely straight forward with no hidden tricks :). Yeah yeah I know...
-
Link to the problem on Timus Online Judge This is a Computational Geometry problem. No 3 points lie on the same line and this is a great...
#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;
}