|
?
?
Escape from Tetris Time Limit: 12000/4000 MS (
Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1078 Accepted Submission(s): 274
Problem Description 由于整日整夜地对着这个棋盘，Lele终于走火入魔。每天一睡觉，他就会梦到自己会被人被扔进一个棋盘中，一直找不到出路，然后从梦中惊醒。久而久之，Lele被搞得精神衰弱。梦境是否会成为现实，谁也说不准，不过不怕一万只怕万一。现在Lele每次看到一个棋盘，都会想象一下自己被关进去以后要如何逃生。
Lele碰到的棋盘都是正方形的，其中有些格子是坏的，不可以走，剩下的都是可以走的。只要一走到棋盘的边沿（最外面的一圈），就算已经逃脱了。Lele梦见自己一定会被扔在一个可以走的格子里，但是不确定具体是哪一个，所以他要做好被扔在任意一个格子的准备。
现在Lele请你帮忙，对于任意一个棋盘，找出一个最短的序列，序列里可以包括north(地图里向上),east(地图里向右),south(地图里向下),west(地图里向左)，这四个方向命令。不论Lele被扔在棋盘里的哪个好的格子里，都能按这个序列行走逃出棋盘。
逃脱的具体方法是：不论Lele被扔在哪里，Lele按照序列里的方向命令一个一个地走，每个命令走一格，如果走的时候会碰到坏的格子，则忽略这条命令。当然，如果已经逃脱了，就可以不考虑序列中剩下的命令了。
Input 本题目包含多组测试，请处理至文件结束。
每组测试第一行包含一个正整数 N (0
接下来有N行，每行N个字符代表这个棋盘。
其中0代表该位置是好的，可以走，1代表该位置是坏的，不可以走。
题目数据保证，对于任意一个棋盘，都存在题目中所要求的序列
Output 对于每组数据，输出题目所要求的序列，序列中每个元素一行。
如果存在两个符合要求的序列，请输出字典序最小的那个序列。
两个测试之间请用一个空行隔开。
Sample Input
4
1101
0001
1100
1001
Sample Output
east
north
Author linle
Source HDOJ 2007 Summer Exercise（2）
Recommend lcy | We have carefully selected several similar problems for you: 1560 1667 1043 1401 2517
题目大意：给一个n*n的棋牌，0可以走，1不可以走，可以上下左右四个方向走，最终输出满足条件的序列。 特别注意： 1、只要逃到棋盘的边缘（最外面一圈）就算已经逃脱。 2、如果存在两个符合要求的序列，请输出字典序最小的那个序列。 3、不要出现PE
详见代码。
#include
#include
#include
#include
#define INF 1<<30 using namespace std; int dir[4][2]= {0,1,-1,0,1,0,0,-1}; int n,minval[10][10];//表示每个点到边距的最短距离 char str[10][10]; int k,want; char dd[4][10] = {east,north,south,west}; int route[1000];//用来存路径 struct node { int x; int y; } s; queue
q,qq; void bfs()//找到每个点到底边界的步数 { node ss; //q.push(s); while (!q.empty()) { s=q.front(); q.pop(); for (int i=0; i<4; i++) { ss.x=s.x+dir[i][0]; ss.y=s.y+dir[i][1]; if (ss.x<0||ss.x>=n||ss.y<0||ss.y>=n) continue; if(!str[ss.x][ss.y]) continue; if (minval[ss.x][ss.y]>minval[s.x][s.y]+1) { minval[ss.x][ss.y]=minval[s.x][s.y]+1; q.push(ss); } } } } int get_h(char s[10][10]) { int mab=0; for (int i=0; i
want) return false; if (dep==want) return true; char tmp[10][10]; for (int i=0; i<4; i++) { memset(tmp,0,sizeof(tmp)); for (int x=0; x
?
?
|