1 条题解
-
0
#include<bits/stdc++.h> #define inf 999999999 #define ll long long using namespace std; struct point { int x,y; friend bool operator == (point a,point b){ return (a.x==b.x && a.y==b.y); } }; struct node { char way; int num; }; point s,e; int n,m; int a[110][110]; int dis[110][110]; queue<point>q; int tox[4]={-1,0,1,0}; int toy[4]={0,1,0,-1}; deque<node>ans; int main() { scanf("%d%d\n",&n,&m); n=n*2-1; m=m*2-1; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { dis[i][j]=-1; char c; c=getchar(); if(c=='.')continue; else if(c=='+')a[i][j]=2; else if(c=='S')s.x=i,s.y=j,a[i][j]=2; else if(c=='E')e.x=i,e.y=j,a[i][j]=2; else a[i][j]=1; }getchar(); } dis[s.x][s.y]=0; point t; t=s; q.push(t); while(!q.empty()) { t=q.front(); q.pop(); if(t==e)break; for(int i=0; i<4; i++) { point t1=t; t1.x+=tox[i]; t1.y+=toy[i]; if(t1.x<1 || t1.x>n || t1.y<1 || t1.y>m || a[t1.x][t1.y]==0 || dis[t1.x][t1.y]!=-1)continue; dis[t1.x][t1.y]=dis[t.x][t.y]+1; q.push(t1); } } int last=-1; int sum=0; t=e; while(1) { if(t==s) { node tt; if(last==0)tt.way='S'; if(last==1)tt.way='W'; if(last==2)tt.way='N'; if(last==3)tt.way='E'; tt.num=sum; ans.push_front(tt); break; } int to; if(a[t.x][t.y]==2)sum++; for(int i=0; i<4; i++) { point t1=t; t1.x+=tox[i]; t1.y+=toy[i]; if(t1.x<1 || t1.x>n || t1.y<1 || t1.y>m || a[t1.x][t1.y]==0 || dis[t1.x][t1.y]!=dis[t.x][t.y]-1)continue; to=i; break; } if(last!=to) { if(last!=-1) { node tt; if(last==0)tt.way='S'; if(last==1)tt.way='W'; if(last==2)tt.way='N'; if(last==3)tt.way='E'; tt.num=sum-1; ans.push_front(tt); sum=1; } last=to; } t.x+=tox[to]; t.y+=toy[to]; } for(int i=0; i<ans.size(); i++) { printf("%c %d\n",ans[i].way,ans[i].num); } return 0; }
- 1
信息
- ID
- 1687
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 1
- 已通过
- 1
- 上传者