IDA*搜索。。。

Escape from Tetris

Time Limit: 12000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 730 Accepted Submission(s): 162

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

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 2234 2517

#include 
   
    
#include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; ///east north south west const int dir_x[4]={0,-1,1,0}; const int dir_y[4]={1,0,0,-1}; int n; struct NODE { int x,y,t; }; bool isBOUND(NODE dian) { if(dian.x==1||dian.y==n||dian.x==n||dian.y==1) return true; return false; } struct MAP { int m[10][10]; void clear(){memset(m,0,sizeof(m));} MAP() {clear();} }M; int minCOST[10][10]; void bfs(int x,int y) { int time=0; bool vis[10][10]; memset(vis,0,sizeof(vis)); queue
        
          q; q.push((NODE){x,y,0}); while(!q.empty()) { NODE u=q.front(),v; q.pop(); if(isBOUND(u)) { time=u.t; break; } for(int i=0;i<4;i++) { v=u;v.t=u.t+1; v.x=v.x+dir_x[i]; v.y=v.y+dir_y[i]; if(M.m[v.x][v.y]==0&&vis[v.x][v.y]==false) { vis[v.x][v.y]=true; q.push((NODE){v.x,v.y,v.t}); } } } minCOST[x][y]=time; } int deepth=0,mindist; int h(MAP u,int& OK) { int ret=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(u.m[i][j]==0) { if(i>=2&&i<=n-1&&j>=2&&j<=n-1) { OK=1; } ret=max(ret,minCOST[i][j]); } } } return ret; } int ans[1000]; bool dfs(int deep,MAP u) { int OK=0; if(deep+h(u,OK)>deepth) return false; if(OK==0) return true; for(int i=0;i<4;i++) { MAP v; for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) v.m[j][k]=1; ans[deep]=i; for(int j=1;j<=n;j++) { for(int k=1;k<=n;k++) { if(u.m[j][k]==0) { if(isBOUND((NODE){j,k,0})) { v.m[j][k]=0; continue; } int X=j+dir_x[i],Y=k+dir_y[i]; if(M.m[X][Y]==0) { v.m[X][Y]=0; } else v.m[j][k]=0; } } } if(dfs(deep+1,v)) return true; } return false; } int main() { int first=1; while(scanf("%d",&n)!=EOF) { mindist=0; if(first) first=0; else putchar(10); for(int i=1;i<=n;i++) { char str[10]; scanf("%s",str); for(int j=0;j

HDOJ 1813 Escape from Tetris

Escape from Tetris