1 /*
2 题意：求从(1, 1)走到(n, m)的二进制路径值最小
3 BFS+贪心：按照标程的作法，首先BFS搜索所有相邻0的位置，直到1出现。接下去从最靠近终点的1开始，
4 每一次走一步，不走回头路，只往下或往右走。因为满足i = j + (i - j)的坐标(j, i - j)可能不止一个，选择最小的访问
5 */
6 #include <cstdio>
7 #include <algorithm>
8 #include <cstring>
9 #include <cmath>
10 #include <queue>
11 #include <vector>
12 using namespace std;
13
14 const int MAXN = 1e3 + 10;
15 const int INF = 0x3f3f3f3f;
16 int dx[4] = {0, 1, 0, -1};
17 int dy[4] = {1, 0, -1, 0};
18 char maze[MAXN][MAXN];
19 bool vis[MAXN][MAXN];
20 int n, m;
21
22 bool judge(int x, int y) {
23 if (x < 1 || x > n || y < 1 || y > m || vis[x][y]) return false;
24 return true;
25 }
26
27 void BFS(void) {
28 memset (vis, false, sizeof (vis)); int mx = 2;
29 queue<pair<int, int> > Q; Q.push (make_pair (1, 1)); vis[1][1] = true;
30 while (!Q.empty ()) {
31 int x = Q.front ().first, y = Q.front ().second; Q.pop ();
32 if (maze[x][y] == '0') {
33 for (int i=0; i<4; ++i) {
34 int tx = x + dx[i], ty = y + dy[i];
35 if (!judge (tx, ty)) continue;
36 mx = max (mx, tx + ty);
37 Q.push(make_pair (tx, ty)); vis[tx][ty] = true;
38 }
39 }
40 }
41
42 if (vis[n][m] && maze[n][m] == '0') {
43 puts ("0"); return ;
44 }
45
46 printf ("1");
47 for (int i=mx; i<n+m; ++i) {
48 char mn = '1';
49 for (int j=1; j<=n; ++j) {
50 if (1 <= i - j && i - j <= m && vis[j][i-j]) {
51 mn = min (mn, maze[j+1][i-j]);
52 mn = min (mn, maze[j][i-j+1]);
53 }
54 }
55 printf ("%c", mn);
56 for (int j=1; j<=n; ++j) {
57 if (1 <= i - j && i - j <= m && vis[j][i-j]) {
58 if (maze[j+1][i-j] == mn) vis[j+1][i-j] = true;
59 if (maze[j][i-j+1] == mn) vis[j][i-j+1] = true;
60 }
61 }
62 }
63 puts ("");
64 }
65
66 int main(void) { //HDOJ 5335 Walk Out
67 //freopen ("I.in", "r", stdin);
68 int T; scanf ("%d", &T);
69 while (T--) {
70 scanf ("%d%d", &n, &m);
71 for (int i=1; i<=n; ++i) scanf ("%s", maze[i] + 1);
72 for (int i=1; i<=n; ++i) maze[i][0] = maze[i][m+1] = '2';
73 for (int i=0; i<=m+1; ++i) maze[0][i] = maze[n+1][i] = '2';
74 BFS ();
75 }
76
77 return 0;
78 }
BFS+贪心 HDOJ 5335 Walk Out
编译人生，运行世界！