Robots

Your company provides robots that pick up litter from a field after sporting events and concerts. Before robots are assigned to a job, an aerial photograph of the field is overlaid with a grid, and every grid cell that contains garbage is marked. All robots begin in the Northwest corner and finish in the Southeast corner. A robot can move in only two directions: East or South. When a robot enters a cell that contains garbage, it picks the garbage up before continuing. Once a robot reaches the Southeast corner it cannot be repositioned or reused. Because your cost is directly proportional to the number of robots used for a job, you want to find the minimum number of robots that can clean a given field.

For example, consider the field map in Figure 1, with rows and columns numbered as shown and garbage cells marked with a 'G'. Here every robot starts at location (1, 1) and ends at location (6, 7).

Figure 1 - A Field Map

Figure 2 shows two possible solutions; the second is preferable because it uses two robots instead of three.

Figure 2 - Two Possible Solutions

Write a program that determines the minimum number of robots needed to pick up all the garbage from a field.

The input consists of one or more field maps, followed by a line containing -1 -1 that signals the end of the input. Each field map consists of one or more lines, each containing one garbage location, followed by a line containing 0 0 that signals the end of that map. A garbage location is given as two integers, the row and the column, separated by a single space. Rows and columns are numbered as shown in Figure 1. The garbage locations are given in row-major order. No single field map has more than 24 rows or 24 columns.

For each field map, print a single line containing the minimum number of robots needed to clean that field.