题目大意:
给你一个起点和一个终点,并且给出了一个起点可以走的方向,问你从起点到终点的最短路径是什么?其中每个点又有四个方向,每个方向还有三种方向(分别是直,左右走)。
分析:
一般我们存迷宫都是用一个二维数组存坐标就行了,但是这个题对应的数组a[x][y]又有四个方向,所以可以想到用a[x][y][d]三维数组存x,y下标对应的方向(因为不一定四个方向一定是有方向的),然后又每个方向上还有三个方向,可以想到用四维数组去描述 a[x][y][4][3],然后就是一个bfs+记录父节点就可以搞定了。
难点:
我之前一直都被卡在四个方向上了,因为对于一个点来说,它要走四个方向上的哪一个取决与它上一个点是怎么来的,比如1 1 去2 1 ,相对于1 1 来说他的方向是上,而对于2 1 来说1 1 来的方向是下,然后每个点都是这样处理起来就会很麻烦,但是其实我一直都被图误导了,图片实际上是按照S(上)W(下)N(左)E(右)这样的方式来存储的,其实我们只需要将四个方向按照NESW(指南针顺时针方向存储),就可以解决这个问题了,这个难点解决了就很好处理了,在NESW方向上扩展FLR方向就行了。
对于不同方向相对的直走左右走都是不同的,我这里我walk就是解决这个问题,至于公式为什么是这样的,只需要按照四个方向枚举一下,然后四个方向上左右走的方向应该是什么样的,然后这个公式就出来了。(做过种类并查集的这个公式都应该是很好推导的)。
打印路径是递归找父节点存vector,然后顺序打印,注意细节。
总结:wf题目确实还是比较难,针对这道题思路不难,但是代码难度比较大,细节非常多,这题感觉还是比较锻炼空间想象能力的,还不错把,第一次接触四维数组。
代码:
#include<iostream>
#include<queue>
#include<cstring>
#include<string>
#include<vector>
#include<cstring>
using namespace std;
/* SAMPLE 3 1 N 3 3 1 1 WL NR * 1 2 WLF NR ER * 1 3 NL ER * 2 1 SL WR NF * 2 2 SL WF ELF * 2 3 SFR EL * 0 */
const int maxn=10;
struct Node{
int x,y,z;
Node(int a,int b,int c):x(a),y(b),z(c){}
Node(){}
};
Node f[maxn][maxn][maxn];
int r0, c0, r1, c1, r2, c2;
char ch,str3[105];
int temped;
const char str1[]="NESW";
const char str2[]="FLR";
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int step[maxn][maxn][maxn];
int maze[maxn][maxn][4][3];
int d[maxn][maxn][maxn];
int dir_id(char c){
return strchr(str1,c)-str1;
}
int turn_id(char c){
return strchr(str2,c)-str2;
}
bool insede(int c,int r){
return (c>=1&&c<=9&&r>=1&&r<=9);
}
Node walk(Node s,int i){
int dirt=s.z;
if(i==1){
dirt=(dirt+3)%4;
}
if(i==2){
dirt=(dirt+1)%4;
}
return Node(s.x+dir[dirt][0],s.y+dir[dirt][1],dirt);
}
bool inside(int r,int c){
return (r>=1&&r<=9&&c>=1&&c<=9);
}
void print(Node s){
vector<Node>st;
for(;;){
st.push_back(s);
if(d[s.x][s.y][s.z]==0)break;
s=f[s.x][s.y][s.z];
}
st.push_back(Node(r0,c0,0));
int cnt=0;
for(int i=st.size()-1;i>=0;i--){
if(cnt % 10 == 0) cout << " ";
cout<<" ("<<st[i].x<<","<<st[i].y<<")";
if(++cnt%10==0)
cout<<endl;
}
if(st.size() % 10 != 0) cout << endl;
}
void bfs(){
memset(d,-1,sizeof(d));
queue<Node>st;
st.push(Node(r1,c1,temped));
d[r1][c1][temped]=0;
while(!st.empty()){
Node now=st.front();
st.pop();
if(now.x==r2&&now.y==c2){
print(now);
return ;
}
for(int i=0;i<3;i++){
Node v=walk(now,i);
if(maze[now.x][now.y][now.z][i]&&inside(v.x,v.y)&&d[v.x][v.y][v.z]<0){
d[v.x][v.y][v.z]=d[now.x][now.y][now.z]+1;
f[v.x][v.y][v.z]=now;
st.push(v);
}
}
}
printf(" No Solution Possible\n");
}
int main(){
string str;
while(cin>>str&&str!="END"){
memset(maze,0,sizeof(maze));
cin >> r0 >> c0 >> ch >> r2 >> c2;
temped=dir_id(ch);
r1=r0+dir[temped][0];
c1=c0+dir[temped][1];
int x,y;
while(cin>>x&&x){
cin>>y;
while(cin>>str3){
if(!strcmp(str3,"*"))break;
int d=dir_id(str3[0]);
for(int i=1;i<strlen(str3);i++){
maze[x][y][d][turn_id(str3[i])]=1;
}
}
}
cout<<str<<endl;
bfs();
}
}