Lovely penguins is a tiny game in which the player controls two penguins.
题目链接
The game holds in two 20×20 grids (the left one and the right one), and each has some blocked places.We number the grid in x t h x_{th} xth?row (starting from the up), y t h y_{th} yth? column (starting from the left) {(x,y)}(x,y).
The penguins move in four directions: up, down, left, right, exactly one step once. If its way is blocked, or it reaches the border, then this movement is omitted.
The player also moves the penguins in four directions, but the behavior of the two penguins is mirrored:
L : left penguin moves to left, right penguin moves to right.
R : left penguin moves to right, right penguin moves to left.
U : both move upwards.
D : both move downwards.
An operation can be omitted on one penguin but works on another.
The left penguin starts from {(20,20)}(20,20) and wants to move to {(1,20)}(1,20).The right penguin starts from {(20,1)}(20,1) and wants to move to {(1,1)}(1,1).If both penguin reach there destination, thay win the game.
Find out the shortest way to win the game.If there are many shortest ways to win, find the one with minimum lexicographical order(D<L<R<U).
Note: When one penguin reaches the destination and the other does not, the penguin that has reached the destination may still move out of the destination.
输入描述:
The input consists of 20 lines, each line contains 41 characters, describing the grids, separated by a space.
‘.’ means the grid is empty.
‘#’ means the grid is blocked.
输出描述:
Output 22 lines.
The first line contains the least number of steps to win the game.
The second line contains a string consisting of ‘L’,‘R’,‘U’,‘D’, describing a way to win.
There may be many ways to win, output the one with minimum lexicographical order.
Then output 20 lines, describing the track of the two penguins, mark the track with character ‘A’, and print as input.
题目大意
有两只企鹅分别在左下角与右下角，他们镜像移动，请输出字典序最小的方法，将他们二者都到达左上角与右上角的方案操作打印出来
算法分析
广度优先搜索算法的思想主要是将每种状态用队列储存起来,再对每种状态进行拓展,例如说对于(20,1)这个状态,我们依次上下左右走一步得到除了(19,1)(21,1)(20,0)(20,2)将越界和障碍物外合法进入队列,储存下状态(19,1)(20,2)再依次扩展直到历遍所有可到达点.
对于该题目我们需要做的是输出两只企鹅到达目的地的字典序最短路径(下 左 右 上)的总步数与操作方法以及路径地图,需要注意企鹅走路是镜像的,且可只操作一只企鹅.那么我们还需要记录下当前状态是由哪个状态来转移过来的,在输出时使用深搜打印路径,用语言描述总是那么苍白下面配合代码解释
#include<bits/stdc++.h>
using namespace std;
const int N=25,M=2e5;
struct pg
{
int x,y;
}p1[M],p2[M];//企鹅1 2 的位置状态
char mp1[N][N],mp2[N][N];//企鹅1 2 的地图
bool book[N][N][N][N];//标记已经企鹅1 2的状态
int qu[M];//记录父节点,即由哪个状态转移
int w[4][2]{1,0,0,-1,0,1,-1,0};//枚举下 左 右 上四个方向的x y数组
char nw[5]{'D','L','R','U'},po[M];//对应的方向和记录路径
void dfs(int h,int t)//深搜输出路径
{
mp1[p1[h].x][p1[h].y]='A';//顺便按照题目要求打上标记
mp2[p2[h].x][p2[h].y]='A';
if(h==1)
{
cout<<t<<endl;
return;
}
dfs(qu[h],t+1)
cout<<po[h];
}
int main()
{
for(int i=1;i<=20;i++)//读入地图数据
scanf("%s%s",mp1[i]+1,mp2[i]+1);
p1[1].x=20,p1[1].y=20,p2[1].x=20,p2[1].y=1;//初始化两只企鹅位置
int h=1,t=1;
for(;h<=t;h++ )
{
if(p1[h].x==1&&p1[h].y==20&&p2[h].x==1&&p2[h].y==1)//如果两只企鹅都到达目的地,说明找到一条最短路径
{
dfs(h,0);//深搜输出路径
cout<<endl;
for(int i=1;i<=20;i++)//输出地图
{
for(int j=1;j<=20;j++)
{
cout<<mp1[i][j];
}
cout<<" ";
for(int j=1;j<=20;j++)
{
cout<<mp2[i][j];
}
cout<<endl;
}
return 0;
}
for(int i=0;i<4;i++)//枚举四个方向 优先按照题目要求顺序
{ int t1x,t1y,t2x,t2y;
t1x =p1[h].x+w[i][0];//走后坐标
t1y=p1[h].y+w[i][1];
t2x=p2[h].x+w[i][0];//注意镜像,上下不变,左右相反
t2y=p2[h].y-w[i][1];
if(t1x<1||t1x>20||t1y<1||t1y>20||mp1[t1x][t1y]=='#')//判断越界或者障碍
t1x-=w[i][0],t1y-=w[i][1];
if(t2x<1||t2x>20||t2y<1||t2y>20||mp2[t2x][t2y]=='#')
t2x-=w[i][0],t2y+=w[i][1];
if(book[t1x][t1y][t2x][t2y])continue;//当前状态已经存在,跳过
book[t1x][t1y][t2x][t2y]=1;
t++;//新状态储存
p1[t].x=t1x,p1[t].y=t1y,p2[t].x=t2x,p2[t].y=t2y;
qu[t]=h,po[t]=nw[i];//记录父节点,以及当前节点是往哪里走的
}
}
}