4016 - 寻宝
在一个网格世界中，其中一个目标单元中有一箱宝藏。有一张藏宝图，图上标注了网格世界的每个单元到目标单元的曼哈顿距离。例如，一个8*8的网格世界的藏宝图如下
|
10 |
9 |
8 |
7 |
6 |
5 |
6 |
7 |
|
9 |
8 |
7 |
6 |
5 |
4 |
5 |
6 |
|
8 |
7 |
6 |
5 |
4 |
3 |
4 |
5 |
|
7 |
6 |
5 |
4 |
3 |
2 |
3 |
4 |
|
6 |
5 |
4 |
3 |
2 |
1 |
2 |
3 |
|
5 |
4 |
3 |
2 |
1 |
0 |
1 |
2 |
|
6 |
5 |
4 |
3 |
2 |
1 |
2 |
3 |
|
7 |
6 |
5 |
4 |
3 |
2 |
3 |
4 |
宝藏位于单元(6,6)，该单元的曼哈顿距离是0。假设每走一步可以移动到邻近的单元，任何单元到目标单元的曼哈顿距离是从该单元移动到目标单元需要的步数。 设计一个降治算法找出宝藏所在位置。
题目输入
输入包含多组数据。每组数据的第一行有两个整数m和n(102 <= m, n <= 103)，分别代表一个网格世界的行数和列数。m = n = 0意味着输入结束。接下来有m行，每一行有n个整数。每个整数代表相应单元的曼哈顿距离。
题目输出
对于每组数据，输出藏有宝藏的目标单元的坐标。
输入/输出样例
题目输入
8 8 10 9 8 7 6 5 6 7 9 8 7 6 5 4 5 6 8 7 6 5 4 3 4 5 7 6 5 4 3 2 3 4 6 5 4 3 2 1 2 3 5 4 3 2 1 0 1 2 6 5 4 3 2 1 2 3 7 6 5 4 3 2 3 4 0 0
题目输出
6 6
C语言解答
#include<stdio.h> #include<stdlib.h> #include<string.h> int main() { int m, n; int i, j; int a[1000][1000]; int r, c, rl, ru, cl, cu; scanf("%d%d", &m, &n); while (m != 0 && n != 0) { for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { scanf("%d", &a[i][j]); } } rl = 0; ru = m - 1; cl = 0; cu = n - 1; while (1) { r = (rl + ru) / 2; c = (cl + cu) / 2; if (a[r][c] == 0) break; if (a[r][c] > a[r - 1][c]) { if (a[r][c] < a[r][c - 1]) { ru = r - 1; cl = c + 1; } else if (a[r][c] > a[r][c - 1]) { ru = r - 1; cu = c - 1; } } if (a[r][c] < a[r - 1][c]) { if (a[r][c] < a[r][c - 1]) { rl = r + 1; cl = c + 1; } else if (a[r][c] > a[r][c - 1]) { rl = r + 1; cu = c - 1; } } } printf("%d %d\n", (r + 1), (c + 1)); scanf("%d%d", &m, &n); } return 0; }