• 题目：Penguins

• 题意：给出两张20 * 20的地图，起点1为(20, 20)，起点2为(20, 1)，终点1为(1, 20)，终点2为(1, 1)，两个企鹅需要分别从起点1->终点1、起点2->终点2，若企鹅1向上或向下走，企鹅2执行相同操作，若企鹅1向左或向右走，则企鹅2执行相反操作，求企鹅1到达终点1且企鹅同时到达终点2的最短路径（若存在多条最短路径，则输出字典序最小的路径），并将每次操作方向、以及走过的路径输出（将这两张图输出即可，只需要将走过的路径标记为'A'）。
• 解析：这道题思路很显然用广搜，首先需要开一个四维数组（或结构体）记录两个企鹅的位置，按照"D、L、R、U"的顺序进行广搜, 每次搜到下一个结点位置则记录其上一个结点位置，并记录到下一个结点所进行的操作（下、左、右、上），这个记录必须记录在下一个结点的信息上，若记录在当前结点信息上则会被不断的更新覆盖，最后无法通过递归的方式去查找路径。
  ps：若其中一只企鹅下一个结点无法到达（碰墙、碰障碍）则需要让其回到原来位置（或者说是原地不动），另一只企鹅可以继续其操作。
• 代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
const int N = 25;
char g1[N][N], g2[N][N];
int dir[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
int step = 0;
char op[10] = {'D', 'L', 'R', 'U'};
char p[N][N][N][N]; //记录该位置
char path[10005];
struct Node
{
    int x1, y1, x2, y2;
};
Node pre_node[N][N][N][N]; //该位置上一个点的位置
int dis[N][N][N][N];

bool check1(int x, int y)
{
    if(g1[x][y] == '#' || x < 1 || x > 20 || y < 1 || y > 20) return true;
    return false;
}

bool check2(int x, int y)
{
    if(g2[x][y] == '#' || x < 1 || x > 20 || y < 1 || y > 20) return true;
    return false;
}

void bfs()
{
    queue<Node> q;
    q.push({20, 20, 20, 1});
    dis[20][20][20][1] = 0;
    while(q.size())
    {
        Node t = q.front();
        q.pop();
        if(t.x1 == 1 && t.y1 == 20 && t.x2 == 1 && t.y2 == 1) return;
        for(int i = 0; i < 4; i++)
        {
            int xx1 = t.x1 + dir[i][0], yy1 = t.y1 + dir[i][1];
            if(check1(xx1, yy1)) //碰墙或者遇到障碍
            {
                xx1 -= dir[i][0];
                yy1 -= dir[i][1];
            }
            int xx2 = t.x2 + dir[i][0], yy2 = t.y2 - dir[i][1]; //xx2坐标与xx1坐标变换相同但yy2需要与yy1操作相反
            if(check2(xx2, yy2)) //碰墙或者遇到障碍
            {
                xx2 -= dir[i][0];
                yy2 += dir[i][1];
            }
            if(dis[xx1][yy1][xx2][yy2] == -1) //之前未访问过（保证是最短路径）
            {
                pre_node[xx1][yy1][xx2][yy2] = {t.x1, t.y1, t.x2, t.y2};
                dis[xx1][yy1][xx2][yy2] = dis[t.x1][t.y1][t.x2][t.y2] + 1; //记录当前路径长度
                p[xx1][yy1][xx2][yy2] = op[i]; //记录方向
                q.push({xx1, yy1, xx2, yy2});
            }
        }
    }
}

void find_Path(int x1, int y1, int x2, int y2)
{
    g1[x1][y1] = 'A', g2[x2][y2] = 'A';
    if(x1 == 20 && y1 == 20 && x2 == 20 && y2 == 1) return;
    int xx1 = pre_node[x1][y1][x2][y2].x1;
    int yy1 = pre_node[x1][y1][x2][y2].y1;
    int xx2 = pre_node[x1][y1][x2][y2].x2;
    int yy2 = pre_node[x1][y1][x2][y2].y2;
    find_Path(xx1, yy1, xx2, yy2);
    path[step++] = p[x1][y1][x2][y2];
}

int main()
{
    memset(dis, -1, sizeof dis);
    for(int i = 1; i <= 20; i++) scanf("%s%s", g1[i] + 1, g2[i] + 1);
    bfs();
    find_Path(1, 20, 1, 1); //从终点递归寻找路径
    printf("%d\n%s\n", step, path);
    for(int i = 1; i <= 20; i++)
        printf("%s %s\n", g1[i] + 1, g2[i] + 1);
    return 0;
}