UVa 10102

From Algorithmist
Jump to navigation Jump to search

Problem Number - Problem Name[edit]

http://uva.onlinejudge.org/external/101/10102.html

Summary[edit]

Given a map of M*M and each of its cell is colored by 1,2 or 3. Starting from any cell colored with 1, you are allow to go up,down,left or right in one step to the neighbor cell within the grid. Your goal is to go from cells colored with 1 to cells colored with 3 in the minimal steps, denoted by s, and also s is maximized.

Explanation[edit]

In one words, maximize the minimum distance between any cell colored with 1 to any cell colored with 3.

Gotchas[edit]

The easiest way to solve this problem is not using BFS. It is obvious that the distance between two cell is abs(x1-x2) + abs(y1-y2). Then just store the coordinates of all the cell colored with 1 and also cell colored with 3. Then a nested loop of two is enough to solve this problem.

Notes[edit]

The range of M is not given, but 105 is enough to get AC.

Input[edit]

4
1223
2123
2213
3212
2
12
33
5
12222
22222
22222
22222
22223
5
12221
22223
22222
32222
22222

Output[edit]

3
1
8
3

References[edit]