Escape from Tetris
Time Limit: 12000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1103 Accepted Submission(s): 280
Problem Description
由于整日整夜地对着这个棋盘，Lele终于走火入魔。每天一睡觉，他就会梦到自己会被人被扔进一个棋盘中，一直找不到出路，然后从梦中惊醒。久而久之，Lele被搞得精神衰弱。梦境是否会成为现实，谁也说不准，不过不怕一万只怕万一。现在Lele每次看到一个棋盘，都会想象一下自己被关进去以后要如何逃生。
Lele碰到的棋盘都是正方形的，其中有些格子是坏的，不可以走，剩下的都是可以走的。只要一走到棋盘的边沿（最外面的一圈），就算已经逃脱了。Lele梦见自己一定会被扔在一个可以走的格子里，但是不确定具体是哪一个，所以他要做好被扔在任意一个格子的准备。
现在Lele请你帮忙，对于任意一个棋盘，找出一个最短的序列，序列里可以包括"north"(地图里向上),"east"(地图里向右),"south"(地图里向下),"west"(地图里向左)，这四个方向命令。不论Lele被扔在棋盘里的哪个好的格子里，都能按这个序列行走逃出棋盘。
逃脱的具体方法是：不论Lele被扔在哪里，Lele按照序列里的方向命令一个一个地走，每个命令走一格，如果走的时候会碰到坏的格子，则忽略这条命令。当然，如果已经逃脱了，就可以不考虑序列中剩下的命令了。
Lele碰到的棋盘都是正方形的，其中有些格子是坏的，不可以走，剩下的都是可以走的。只要一走到棋盘的边沿（最外面的一圈），就算已经逃脱了。Lele梦见自己一定会被扔在一个可以走的格子里，但是不确定具体是哪一个，所以他要做好被扔在任意一个格子的准备。
现在Lele请你帮忙，对于任意一个棋盘，找出一个最短的序列，序列里可以包括"north"(地图里向上),"east"(地图里向右),"south"(地图里向下),"west"(地图里向左)，这四个方向命令。不论Lele被扔在棋盘里的哪个好的格子里，都能按这个序列行走逃出棋盘。
逃脱的具体方法是：不论Lele被扔在哪里，Lele按照序列里的方向命令一个一个地走，每个命令走一格，如果走的时候会碰到坏的格子，则忽略这条命令。当然，如果已经逃脱了，就可以不考虑序列中剩下的命令了。
Input
本题目包含多组测试，请处理至文件结束。
每组测试第一行包含一个正整数 N (0<N<9)，代表棋盘的大小是 N*N
接下来有N行，每行N个字符代表这个棋盘。
其中0代表该位置是好的，可以走，1代表该位置是坏的，不可以走。
题目数据保证，对于任意一个棋盘，都存在题目中所要求的序列
每组测试第一行包含一个正整数 N (0<N<9)，代表棋盘的大小是 N*N
接下来有N行，每行N个字符代表这个棋盘。
其中0代表该位置是好的，可以走，1代表该位置是坏的，不可以走。
题目数据保证，对于任意一个棋盘，都存在题目中所要求的序列
Output
对于每组数据，输出题目所要求的序列，序列中每个元素一行。
如果存在两个符合要求的序列，请输出字典序最小的那个序列。
两个测试之间请用一个空行隔开。
如果存在两个符合要求的序列，请输出字典序最小的那个序列。
两个测试之间请用一个空行隔开。
Sample Input
4
1101
0001
1100
1001
Sample Output
east
north
Author
linle
Source
Recommend
题目大意：给一个n*n的棋牌，0可以走，1不可以走，可以上下左右四个方向走，最终输出满足条件的序列。
思路：迭代加深搜索，在搜索的过程中按字典序依次选择四种操作，然后将所有的空格统一执行这个移动操作，如果最终所有空格都移到了边缘，那么就说明找到了最优的深度同时也找到了字典序最优的操作序列。
在搜索的时候可以加一个有效的剪枝：先bfs预处理出每个空格移到边缘所需的最少步数，这样如果在搜索过程中发现某个空格即便按最快的方案移动都不能在迭代加深限制的步数内到达边缘的话，就可以剪枝了。
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #include<queue> 5 #define MAXN 10 6 #define MAXD 40 7 #define INF 0x3f3f3f3f 8 int dx[] = { 0, -1, 1, 0 }, dy[] = { 1, 0, 0, -1 }; 9 int N, M, g[MAXN][MAXN], ix[MAXD], iy[MAXD], dis[MAXN][MAXN]; 10 int list[1010]; 11 inline int inedge(int x, int y) { 12 return x == 1 || x == N || y == 1 || y == N; 13 } 14 int bfs(int sx, int sy) { 15 int i, x, y, nx, ny, d[MAXN][MAXN]; 16 memset(d, -1, sizeof(d)); 17 std::queue <int> q; 18 d[sx][sy] = 0, q.push(sx * 10 + sy); 19 while (!q.empty()) { 20 x = q.front() / 10, y = q.front() % 10, q.pop(); 21 if (inedge(x, y)) return d[x][y]; 22 for (i = 0; i < 4; i++) { 23 nx = x + dx[i], ny = y + dy[i]; 24 if (g[nx][ny] && d[nx][ny] == -1) 25 d[nx][ny] = d[x][y] + 1, q.push(nx * 10 + ny); 26 } 27 } 28 return 0; 29 } 30 void init() { 31 int i, j; 32 char b[MAXD]; 33 for (i = 1; i <= N; i++) { 34 scanf("%s", b + 1); 35 for (j = 1; j <= N; j++) g[i][j] = 1 - (b[j] - '0'); // 将0、1反转。 36 } 37 M = 0; 38 for (i = 1; i <= N; i++) 39 for (j = 1; j <= N; j++) { 40 if (g[i][j]) { 41 if (inedge(i, j)) dis[i][j] = 0; 42 else { 43 dis[i][j] = bfs(i, j); // dis[i][j]表示这个点移动到边界的最小移动步数 44 ix[M] = i, iy[M] = j, ++M;//ix，iy数组记录需要移动的点。M表示需要移动的点的个数。 45 } 46 } else dis[i][j] = INF; 47 } 48 } 49 int Max(int *x, int *y) { 50 int i, ans = 0; 51 for (i = 0; i < M; i++) ans = std::max(ans, dis[x[i]][y[i]]); 52 return ans; 53 } 54 int dfs(int d, int *ix, int *iy) { 55 if (Max(ix, iy) > d) return 0; // 很重要的一步，剪枝。 56 if (d == 0) return 1; 57 int i, j, x[MAXD], y[MAXD], nx, ny; 58 for (i = 0; i < 4; i++) { 59 list[d] = i; 60 for (j = 0; j < M; j++) { 61 nx = ix[j] + dx[i], ny = iy[j] + dy[i]; //移动到新的点nx，ny。 62 if (inedge(ix[j], iy[j]) || g[nx][ny] == 0) 63 x[j] = ix[j], y[j] = iy[j]; 64 else 65 x[j] = nx, y[j] = ny; //将移动到的新的点记录在x、y数组中。 66 } 67 if (dfs(d - 1, x, y)) return 1; 68 } 69 return 0; 70 } 71 void solve() { 72 int i, dep; 73 if (M == 0) return; 74 for (dep = 1; !dfs(dep, ix, iy); dep++); 75 for (i = dep; i > 0; i--) { 76 if (list[i] == 0) puts("east"); 77 else if (list[i] == 1) puts("north"); 78 else if (list[i] == 2) puts("south"); 79 else puts("west"); 80 } 81 } 82 int main() { 83 int t = 0; 84 while (scanf("%d", &N) == 1) { 85 init(); 86 if (t++) printf(" "); 87 solve(); 88 } 89 return 0; 90 }