首页 > 代码库 > 【分类讨论】【spfa】【BFS】Codeforces Round #416 (Div. 2) D. Vladik and Favorite Game
【分类讨论】【spfa】【BFS】Codeforces Round #416 (Div. 2) D. Vladik and Favorite Game
那个人第一步肯定要么能向下走,要么能向右走。于是一定可以判断出上下是否对调,或者左右是否对调。
然后他往这个方向再走一走就能发现一定可以再往旁边走,此时就可以判断出另一个方向是否对调。
都判断出来以后,跑个spfa或者bfs就行了。
细节较多……有一些边界情况需要处理。比如终点在第一行或者第一列的情况。
#include<cstdio> #include<queue> #include<cstring> #include<algorithm> using namespace std; typedef pair<int,int> Point; Point ma[110*110*10]; const int dx[]={0,1,0,-1},dy[]={1,0,-1,0}; int n,m,End; char a[110][110]; int num[110][110],pen; queue<int>Q; int dis[110*110*10],v[110*110*4*10],e,__next[110*110*4*10],first[110*110*10]; int pre[110*110*10]; bool inq[110*110*10]; void AddEdge(int U,int V){ v[++e]=V; __next[e]=first[U]; first[U]=e; } void spfa(const int &s) { memset(dis,0x7f,sizeof(dis)); dis[s]=0; Q.push(s); inq[s]=1; while(!Q.empty()) { int U=Q.front(); for(int i=first[U];i;i=__next[i]) if(dis[v[i]]>dis[U]+1) { dis[v[i]]=dis[U]+1; pre[v[i]]=U; if(!inq[v[i]]) { Q.push(v[i]); inq[v[i]]=1; } } Q.pop(); inq[U]=0; } } Point path[110*110*10]; int p; bool lr,ud; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i){ scanf("%s",a[i]+1); } for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ num[i][j]=++pen; ma[pen]=make_pair(i,j); if(a[i][j]==‘F‘){ End=num[i][j]; } } } for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j)if(a[i][j]==‘.‘ || a[i][j]==‘F‘){ for(int k=0;k<4;++k){ int tx=i+dx[k],ty=j+dy[k]; if(a[tx][ty]==‘.‘ || a[tx][ty]==‘F‘){ AddEdge(num[i][j],num[tx][ty]); } } } } if(End==1){ return 0; } int x,y; if((a[2][1]==‘*‘ || n==1) && (a[1][2]==‘.‘ || a[1][2]==‘F‘)){ puts("R"); fflush(stdout); scanf("%d%d",&x,&y); if(x==1 && y==1){ lr=1; } while(a[x][y]!=‘F‘ && a[x+1][y]==‘*‘){ puts(lr ? "L" : "R"); fflush(stdout); scanf("%d%d",&x,&y); } if(a[x][y]==‘F‘){ return 0; } puts("D"); fflush(stdout); scanf("%d%d",&x,&y); if(a[x][y]==‘F‘){ return 0; } if(x==1){ ud=1; } } else if((a[1][2]==‘*‘ || m==1) && (a[2][1]==‘.‘ || a[2][1]==‘F‘)){ puts("D"); fflush(stdout); scanf("%d%d",&x,&y); if(x==1 && y==1){ ud=1; } while(a[x][y]!=‘F‘ && a[x][y+1]==‘*‘){ puts(ud ? "U" : "D"); fflush(stdout); scanf("%d%d",&x,&y); } if(a[x][y]==‘F‘){ return 0; } puts("R"); fflush(stdout); scanf("%d%d",&x,&y); if(a[x][y]==‘F‘){ return 0; } if(y==1){ lr=1; } } else if((a[1][2]==‘.‘ || a[1][2]==‘F‘) && (a[2][1]==‘.‘ || a[2][1]==‘F‘)){ puts("R"); fflush(stdout); scanf("%d%d",&x,&y); if(x==1 && y==1){ lr=1; puts("D"); fflush(stdout); scanf("%d%d",&x,&y); if(num[x][y]==End){ return 0; } if(x==1 && y==1){ ud=1; } } else{ if(num[x][y]==End){ return 0; } puts("L"); fflush(stdout); scanf("%d%d",&x,&y); puts("D"); fflush(stdout); scanf("%d%d",&x,&y); if(num[x][y]==End){ return 0; } if(x==1 && y==1){ ud=1; } } } spfa(num[x][y]); int U=End; while(U!=num[x][y]){ path[++p]=ma[U]; U=pre[U]; } path[++p]=ma[num[x][y]]; for(int i=p;i>1;--i){ if(path[i-1].first-path[i].first==1){ puts(ud ? "U" : "D"); fflush(stdout); scanf("%d%d",&x,&y); } if(path[i-1].first-path[i].first==-1){ puts(ud ? "D" : "U"); fflush(stdout); scanf("%d%d",&x,&y); } if(path[i-1].second-path[i].second==1){ puts(lr ? "L" : "R"); fflush(stdout); scanf("%d%d",&x,&y); } if(path[i-1].second-path[i].second==-1){ puts(lr ? "R" : "L"); fflush(stdout); scanf("%d%d",&x,&y); } } return 0; }
【分类讨论】【spfa】【BFS】Codeforces Round #416 (Div. 2) D. Vladik and Favorite Game
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。