本文主要是介绍HDU 1813 Escape from Tetris IDA*,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:由于整日整夜地对着这个棋盘,Lele终于走火入魔。每天一睡觉,他就会梦到自己会被人被扔进一个棋盘中,一直找不到出路,然后从梦中惊醒。久而久之,Lele被搞得精神衰弱。梦境是否会成为现实,谁也说不准,不过不怕一万只怕万一。现在Lele每次看到一个棋盘,都会想象一下自己被关进去以后要如何逃生。
Lele碰到的棋盘都是正方形的,其中有些格子是坏的,不可以走,剩下的都是可以走的。只要一走到棋盘的边沿(最外面的一圈),就算已经逃脱了。Lele梦见自己一定会被扔在一个可以走的格子里,但是不确定具体是哪一个,所以他要做好被扔在任意一个格子的准备。
现在Lele请你帮忙,对于任意一个棋盘,找出一个最短的序列,序列里可以包括"north"(地图里向上),"east"(地图里向右),"south"(地图里向下),"west"(地图里向左),这四个方向命令。不论Lele被扔在棋盘里的哪个好的格子里,都能按这个序列行走逃出棋盘。
逃脱的具体方法是:不论Lele被扔在哪里,Lele按照序列里的方向命令一个一个地走,每个命令走一格,如果走的时候会碰到坏的格子,则忽略这条命令。当然,如果已经逃脱了,就可以不考虑序列中剩下的命令了。如果存在两个符合要求的序列,请输出字典序最小的那个序列。
Lele碰到的棋盘都是正方形的,其中有些格子是坏的,不可以走,剩下的都是可以走的。只要一走到棋盘的边沿(最外面的一圈),就算已经逃脱了。Lele梦见自己一定会被扔在一个可以走的格子里,但是不确定具体是哪一个,所以他要做好被扔在任意一个格子的准备。
现在Lele请你帮忙,对于任意一个棋盘,找出一个最短的序列,序列里可以包括"north"(地图里向上),"east"(地图里向右),"south"(地图里向下),"west"(地图里向左),这四个方向命令。不论Lele被扔在棋盘里的哪个好的格子里,都能按这个序列行走逃出棋盘。
逃脱的具体方法是:不论Lele被扔在哪里,Lele按照序列里的方向命令一个一个地走,每个命令走一格,如果走的时候会碰到坏的格子,则忽略这条命令。当然,如果已经逃脱了,就可以不考虑序列中剩下的命令了。如果存在两个符合要求的序列,请输出字典序最小的那个序列。
想法:有的人可能不需要看题解,但就是wa,先上一个我没注意的坑点,字典序最小,这个条件,我做题目做做就忘了这个条件了,一直wa,由于要字典序最小,所以枚举方向的时候
一定要是east,north,south,west,因为字母的顺序就是ensw,尴尬了,我就没注意永远上北下南左西右东。wa了十几发还不知道错误。
说完这个坑点,就说说思路了:首先我们先找到,每一个点到边界的最短距离,这为之后用到,那么定义dis[i][j],表示(i,j)到边界的最短距离。然后就枚举方向,然后图中每一个可行点都要
朝着这个方向走。如果下一步不通,那么此点原地不动,如果下一步可行,则保存行动之后的点。如果所有点到边界的距离都为0那么,表示存在解,输出即可。
这里有一个减枝if:d+get_h(mat)>step then:return false, get_h()函数返回的是所有点中到达边界最短距离中的最大值,如果加上已有的走的步数大于设定的步数,那就不需要再继续了,直接返回false即可。
一定要是east,north,south,west,因为字母的顺序就是ensw,尴尬了,我就没注意永远上北下南左西右东。wa了十几发还不知道错误。
说完这个坑点,就说说思路了:首先我们先找到,每一个点到边界的最短距离,这为之后用到,那么定义dis[i][j],表示(i,j)到边界的最短距离。然后就枚举方向,然后图中每一个可行点都要
朝着这个方向走。如果下一步不通,那么此点原地不动,如果下一步可行,则保存行动之后的点。如果所有点到边界的距离都为0那么,表示存在解,输出即可。
这里有一个减枝if:d+get_h(mat)>step then:return false, get_h()函数返回的是所有点中到达边界最短距离中的最大值,如果加上已有的走的步数大于设定的步数,那就不需要再继续了,直接返回false即可。
#include<iostream>
#include<cstring>
#include<queue>
#define inf 0x7fffffff
using namespace std;
char map[9][9];
char Dir[4][10] = {"east","north","south","west"};
int dir[4][2] = {0,1,-1,0,1,0,0,-1};
int dis[9][9],path[1000];
int n,step;
struct node
{int x,y;
};
queue<node>q;
bool isedge(int x,int y)
{return x==0||x==n-1||y==0||y==n-1;
}
bool ismap(int i,int j)
{return i>=0&&i<n&&j>=0&&j<n;
}
void bfs()
{node head,tail;while(!q.empty()){head=q.front();q.pop();for(int i=0;i<4;i++){tail.x=head.x+dir[i][0];tail.y=head.y+dir[i][1];if(!map[tail.x][tail.y]) continue;if(!ismap(tail.x,tail.y)) continue;if(dis[tail.x][tail.y]>dis[head.x][head.y]+1){dis[tail.x][tail.y]=dis[head.x][head.y]+1;q.push(tail);}}}
}
void Init()
{while(!q.empty()) q.pop();for(int i=0;i<n;i++){for(int j=0;j<n;j++){dis[i][j]=inf;map[i][j]=map[i][j]=='1'?0:1;if(!map[i][j]) continue;if(isedge(i,j)){dis[i][j]=0;node pp;pp.x=i;pp.y=j;q.push(pp);}}}
}
int get_h(char mat[9][9])
{int Mx=0;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(mat[i][j]) Mx=max(Mx,dis[i][j]);}}return Mx;
}
bool dfs(char mat[9][9],int d)
{if(d+get_h(mat)>step) return false;if(d==step) return true;char nxt[9][9];for(int k=0;k<4;k++){memset(nxt,0,sizeof(nxt));for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(isedge(i,j)||!mat[i][j]) continue;int nx=i+dir[k][0];int ny=j+dir[k][1];if(!map[nx][ny]) nxt[i][j]=1;else nxt[nx][ny]=1;}}path[d]=k;if(dfs(nxt,d+1)) return true;}return false;
}
int main()
{int ca=0;while(~scanf("%d",&n)){if(ca++) cout<<endl;for(int i=0;i<n;i++)scanf("%s",map[i]);Init();bfs();step=0;while(1){if(dfs(map,0)) break;step++;}for(int i=0;i<step;i++){printf("%s\n",Dir[path[i]]);}}return 0;
}
这篇关于HDU 1813 Escape from Tetris IDA*的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!