(Describetion)
(Input)
(Output)
(Sample) (Input)
2 3
10 2 10 10 2 6
3 12 11 14 9 4
13 15 3 6 15 13
14 11 12 9 14 11
0 0
(Sample) (Output)
NESESEENNWNWWWWW
(Hint)
题目大意：有一个(4 imes 6)的迷宫，每个格子会给你一个权值，这个权值是（如果西边有墙）(1)，(2)（北），(4)（东），(8)（南）的和，给定你起点和终点（注意，这里给出的(x,y)并不是真正的(x,y)，仔细看看原文可以发现问题），如果前面没有墙，可以直接走，如果前面有且仅有一堵墙，并且不是边界，可以把墙往前推一格，求至少多少步可以出这个迷宫（出的条件是你在边界并且边界那个方向没有墙），最后如果有多个最小步数的方案，输出答案要按西北东南序排序输出
思路
我们看见最小步数(+)走迷宫，第一眼想到深搜
再看见(4 imes 6)，所以我们选择(IDA*)
我们考虑看到(1,2,4,8)，这几个熟悉的数字，我们联想到二进制，我们可以用与来判断这个格子哪边有墙
当你前面没有墙时，则直接走，如果有墙，先判断前面的前面有没有墙，如果有，则走不了，如果没有，就推墙，这时记得更新三个格子的墙的信息
接下来的就是暴力了
#include<bits/stdc++.h>
using namespace std;
const int nextx[]={0,-1,0,1};
const int nexty[]={-1,0,1,0};
const int N=10;
int way[N][N];
char s[]={'W','N','E','S'};
int ans[30];
int dir[]={1,2,4,8};
bool vis[N][N];
int sx,sy;
bool check(int x,int y)
{
return x>4||x<1||y<1||y>6;
}
int right(int x,int y)//判断是否到了边界并且边界上没墙，即可以出去
{
if((y==1)&&!(way[x][y]&1))return 0;
if((x==1)&&!(way[x][y]&2))return 1;
if((y==6)&&!(way[x][y]&4))return 2;
if((x==4)&&!(way[x][y]&8))return 3;
return -1;
}
bool dfs(int x,int y,int cnt,int maxdep)//IDA*
{
if(cnt>=maxdep)return 0;
int tmp=right(x,y);
if(tmp!=-1)
{
ans[cnt]=tmp;
return 1;
}
for(int i=0;i<4;i++)
{
int xx=x+nextx[i];
int yy=y+nexty[i];
if(check(xx,yy)||vis[xx][yy])continue;
if(!(way[x][y]&dir[i]))
{
vis[xx][yy]=1;
ans[cnt]=i;
if(dfs(xx,yy,cnt+1,maxdep))return 1;
vis[xx][yy]=0;
}
else
{
if(!(way[xx][yy]&dir[i]))
{
way[x][y]-=dir[i];
way[xx][yy]+=dir[i]-dir[(i+2)%4];
if(!check(xx+nextx[i],yy+nexty[i]))way[xx+nextx[i]][yy+nexty[i]]+=dir[(i+2)%4];
ans[cnt]=i,vis[xx][yy]=1;
if(dfs(xx,yy,cnt+1,maxdep))return 1;
if(!check(xx+nextx[i],yy+nexty[i]))way[xx+nextx[i]][yy+nexty[i]]-=dir[(i+2)%4];
way[x][y]+=dir[i];
way[xx][yy]-=(dir[i]-dir[(i+2)%4]);
vis[xx][yy]=0;
}
}
}
return 0;
}
int main()
{
// freopen("testdata7.in","r",stdin);
// freopen("testdata7.out","w",stdout);
while(scanf("%d %d",&sy,&sx)&&(sx||sy))
{
memset(ans,0,sizeof(ans));
for(int i=1;i<=4;i++)
{
for(int j=1;j<=6;j++)
{
scanf("%d",&way[i][j]);
}
}
for(int dep=1;;dep++)
{
memset(vis,0,sizeof(vis));
vis[sx][sy]=1;
if(dfs(sx,sy,0,dep))
{
for(int i=0;i<dep;i++)printf("%c",s[ans[i]]);
puts("");
break;
}
}
}
return 0;
}
/*
4 1
4 15 10 14 9 10
10 14 3 10 6 4
5 2 11 9 7 15
8 2 8 3 2 15
0 0
*/