hdu 1813（IDA*算法+dfs）
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;
queueq,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; iwant)
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
