Penguins

Penguins

题意：

有两个20*20的地图，有障碍物，两个地图各有一个小人，左侧地图的小人要从右下角走到右上角，右侧地图的小人要从左下角走到左上角，这两个小人是镜像移动的，

左侧小人	右侧小人
左移动	右移动
右移动	左移动
上移动	上移动
下	下

现在问最短路径是多少，且输出移动情况，并要求移动的字典序最小
(D<L<R<U)

题解：

BFS模拟，两个人同步移动
没啥说的，就是纯BFS模拟过程，详细看代码

代码 ：

#include<bits/stdc++.h>
using namespace std;
const int maxn=20+10;
//string mp1[maxn];
//string mp2[maxn];
char mp[2][maxn][maxn];
char mp1[maxn][maxn];
char mp2[maxn][maxn];
int vis[maxn][maxn][maxn][maxn];
int turn[4][2]={0,-1,0,1,-1,0,1,0};
int turn2[4][2]={0,1,0,-1,-1,0,1,0};
struct node{int x1,y1,x2,y2;string s;
}; 
char ss[15]="LRUD";
bool check(int x1,int y1,int id)
{if(x1>20||y1>20||x1<=0||y1<=0)return 0;if(mp[id-1][x1][y1]=='#'){return 0;}return 1;}
node ans;
int len=0;
int bfs()
{queue<node >q;node t1;t1={20,20,20,1,""};q.push(t1);while(!q.empty()){node now=q.front();q.pop();if(vis[now.x1][now.y1][now.x2][now.y2]==1)continue;vis[now.x1][now.y1][now.x2][now.y2]=1;if(now.x1==1&&now.y1==20&&now.x2==1&&now.y2==1){ans=now;return now.s.size();}for(int i=0;i<4;i++){int nx1,ny1,nx2,ny2;nx1=now.x1+turn[i][0];ny1=now.y1+turn[i][1];nx2=now.x2+turn2[i][0];ny2=now.y2+turn2[i][1];if(check(nx1,ny1,1)==0&&check(nx2,ny2,2)==0)//左右都不能走 {continue;}if(check(nx1,ny1,1)==1&&check(nx2,ny2,2)==0)//左边能走，右边不能走 {t1={nx1,ny1,now.x2,now.y2,now.s+ss[i]};q.push(t1);}if(check(nx1,ny1,1)==0&&check(nx2,ny2,2)==1)//右边能走 {t1={now.x1,now.y1,nx2,ny2,now.s+ss[i]};q.push(t1);}if(check(nx1,ny1,1)==1&&check(nx2,ny2,2)==1){t1={nx1,ny1,nx2,ny2,now.s+ss[i]};q.push(t1);}}}}
void pr()
{mp[0][20][20]='A';mp[1][20][1]='A';int nx1,ny1,nx2,ny2;nx1=20,ny1=20,nx2=20,ny2=1;for(int i=1;i<=len;i++){if(ans.s[i-1]=='L'){if(check(nx1+turn[0][0],ny1+turn[0][1],1))//左侧可以走 {nx1=nx1+turn[0][0];ny1=ny1+turn[0][1];}if(check(nx2+turn2[0][0],ny2+turn2[0][1],2))//右侧可以走 {nx2=nx2+turn2[0][0];ny2=ny2+turn2[0][1];}}else if(ans.s[i-1]=='R'){if(check(nx1+turn[1][0],ny1+turn[1][1],1)){nx1=nx1+turn[1][0];ny1=ny1+turn[1][1];}if(check(nx2+turn2[1][0],ny2+turn2[1][1],2)){nx2=nx2+turn2[1][0];ny2=ny2+turn2[1][1];}}else if(ans.s[i-1]=='U'){if(check(nx1+turn[2][0],ny1+turn[2][1],1)){nx1=nx1+turn[2][0];ny1=ny1+turn[2][1];}if(check(nx2+turn2[2][0],ny2+turn2[2][1],2)){nx2=nx2+turn2[2][0];ny2=ny2+turn2[2][1];}} else{if(check(nx1+turn[3][0],ny1+turn[3][1],1)){nx1=nx1+turn[3][0];ny1=ny1+turn[3][1];}if(check(nx2+turn2[3][0],ny2+turn2[3][1],2)){nx2=nx2+turn2[3][0];ny2=ny2+turn2[3][1];}}mp[0][nx1][ny1]='A';mp[1][nx2][ny2]='A';}
}
int main()
{for(int i=1;i<=20;i++){scanf("%s %s",mp[0][i]+1, mp[1][i]+1);}//mp[0]表示左侧图，mp[1]表示右侧图 len=bfs();cout<<len<<endl;cout<<ans.s<<endl;pr();//标记移动路径 for(int i=1;i<=20;i++){for(int j=1;j<=20;j++){cout<<mp[0][i][j];}cout<<" ";for(int j=1;j<=20;j++){cout<<mp[1][i][j];}cout<<endl;} return 0;
}