# UVa 10102

## Contents

## 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