uva816 Abbott’s Revenge

本文主要是介绍uva816 Abbott’s Revenge，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

自己写的，测试了好多数据都行，但是WA，望大神指出错误

#include<bits/stdc++.h>
#include<stdio.h>
#include<cstring>
using namespace std;
int edge[10][10][5][5];
int xx[10][10][5];
int dir1[5][2];
struct node
{int x;int y;int dir;int pi;
};
int visit[10][10][5][5],visit1[10][10][5];
node p[10][10][5];
node path[1005];
map<char,int>d;
string str;
char name[105];
int openx,openy,endx,endy,sum=0,flag=0;
char di;
node now,open;
int work(int dir,int j)
{int d;switch(dir){case 1:if(j==1) d=4;else if(j==2) d=1;else if(j==3) d=2;break;case 2:if(j==1) d=1;else if(j==2) d=2;else if(j==3) d=3;break;case 3:if(j==1) d=2;else if(j==2) d=3;else if(j==3) d=4;break;case 4:if(j==1) d=3;else if(j==2) d=4;else if(j==3) d=1;break;}return d;
}
void bfs()
{int dr,r;memset(visit,0,sizeof(visit));queue<node>q;node op,n;op.x=openx;op.y=openy;op.dir=d[di];dr=work(op.dir,2);r=op.dir+2;op.pi=2;if(r%4==0)r=4;elser%=4;flag=0;n.x=openx+dir1[r][0];n.y=openy+dir1[r][1];n.dir=dr;n.pi=2;if(n.x==endx&&n.y==endy){flag=1;now=n;p[n.x][n.y][n.dir]=op;open=op;return;}else if(n.x>=1&&n.x<=9&&n.y>=1&&n.y<=9&&xx[n.x][n.y][n.dir]){open=n;p[n.x][n.y][n.dir]=op;q.push(n);}while(!q.empty()){node temp=q.front();q.pop();for(int j=1;j<=3;j++){if(edge[temp.x][temp.y][temp.dir][j]){visit[temp.x][temp.y][temp.dir][j]=1;temp.pi=j;dr=work(temp.dir,j);r=temp.dir+j;if(r%4==0)r=4;elser%=4;n.x=temp.x+dir1[r][0];n.y=temp.y+dir1[r][1];n.dir=dr;n.pi=j;if(n.x==endx&&n.y==endy){flag=1;now=n;p[n.x][n.y][n.dir]=temp;break;}if(n.x>=1&&n.x<=9&&n.y>=1&&n.y<=9&&xx[n.x][n.y][n.dir]){if(!visit1[n.x][n.y][n.dir]){visit1[n.x][n.y][n.dir]=1;p[n.x][n.y][n.dir]=temp;q.push(n);}}}}if(flag)break;}
}
void print(int pi)
{int sum=0;if(flag){int num=0;while(1){path[++sum]=now;now=p[now.x][now.y][now.dir];if(now.x==open.x&&now.y==open.y&&now.dir==open.dir/*&&num==*/){path[++sum]=now;path[++sum]=p[now.x][now.y][now.dir];break;}}cout<<"  ";for(int i=sum;i>=1;i--){num++;if(!path[i].x&&!path[i].y)continue;if(num==11){num==1;cout<<"\n  ";cout<<'('<<path[i].x<<','<<path[i].y<<") ";}else{cout<<'('<<path[i].x<<','<<path[i].y<<") ";}}cout<<endl;return;}else{cout<<"  No Solution Possible"<<endl;return ;}
}
int main()
{int x,y;dir1[1][0]=0;dir1[1][1]=-1;dir1[2][0]=-1;dir1[2][1]=0;dir1[3][0]=0;dir1[3][1]=1;dir1[4][0]=1;dir1[4][1]=0;d['E']=1;d['S']=2;d['W']=3;d['N']=4;map<char,int>t;t['L']=1;t['F']=2;t['R']=3;while(scanf("%s",name)){if(strcmp(name,"END")==0)break;cout<<name<<endl;cin>>openx>>openy>>di>>endx>>endy;memset(edge,0,sizeof(edge));memset(xx,0,sizeof(xx));memset(visit1,0,sizeof(visit1));int num=0;while(cin>>x){if(x==0)break;cin>>y;while(cin>>str){if(str=="*")break;else{char s=str[0];xx[x][y][d[s]]=1;for(int i=1;i<str.size();i++){edge[x][y][d[s]][t[str[i]]]=1;}}}}bfs();print(d[di]);}return 0;
}

这篇关于uva816 Abbott’s Revenge的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---