Penguins
题面:已知两只企鹅的始末位置,按照题目规则最短路并且有最小字典序。
解析:两只企鹅规定是同时行动,构造一个四维数组来表示两企鹅同时到两点的状态。然后直接bfs求出最短路径。用pre[][][][]数组来记录前驱状态,之后用爆搜终点到起始点,将经过的每个点变为'A',再记录行动方向。
代码(要注意格式)
#include<bits/stdc++.h> using namespace std; struct node{ int x1,y1,x2,y2; }; char m1[25][25],m2[25][25]; int dx[4]={1,0,0,-1}; int dy[2][4]={0,-1,1,0,0,1,-1,0}; char op[4]={'D','L','R','U'}; int vis[25][25][25][25]; int f[25][25][25][25]; node pre[25][25][25][25]; char ans[404]; int num=0; queue<node> q; void bfs(){ memset(vis,0x3f3f3f,sizeof(vis)); vis[20][20][20][1]=0; q.push({20,20,20,1}); while(!q.empty()){ node p=q.front(); q.pop(); int k=vis[p.x1][p.y1][p.x2][p.y2]; for(int i=0;i<4;i++){ int tx1=p.x1+dx[i],ty1=p.y1+dy[0][i]; int tx2=p.x2+dx[i],ty2=p.y2+dy[1][i]; if(m1[tx1][ty1]!='.') { tx1=p.x1;ty1=p.y1; } if(m2[tx2][ty2]!='.'){ tx2=p.x2;ty2=p.y2; } if(k+1<vis[tx1][ty1][tx2][ty2]){ vis[tx1][ty1][tx2][ty2]=k+1; pre[tx1][ty1][tx2][ty2]={p.x1,p.y1,p.x2,p.y2}; f[tx1][ty1][tx2][ty2]=i; q.push({tx1,ty1,tx2,ty2}); } } } } void solve(node s){ node t=pre[s.x1][s.y1][s.x2][s.y2]; m1[s.x1][s.y1]='A'; m2[s.x2][s.y2]='A'; if(s.x1==20&&s.y1==20&&s.x2==20&&s.y2==1) return ; solve(t); ans[num++]=op[f[s.x1][s.y1][s.x2][s.y2]]; return ; } int main(){ for(int i=1;i<=20;i++) scanf("%s%s",m1[i]+1,m2[i]+1); bfs(); solve({1,20,1,1}); printf("%d\n%s\n",num,ans); for(int i=1;i<=20;i++) printf("%s %s\n",m1[i]+1,m2[i]+1); }