题目描述#

两头白天鹅生活在一个部分湖面结了冰的湖泊中，湖面的形状为一个长方形，并且被分割成R行C列的小方格，某些方格中结了冰，这样的方格称之为冰格，其余的方格称之为水格。冬天过去了，湖面上的冰渐渐开始溶解了，每一天与水相邻的冰格就将消融而转化为水格。所谓两个方格相邻是指它们在水平或垂直方向有公共边，两个呈对角的方格是不相邻的，下图给出样例数据的演化过程。

白天鹅只能在水中沿水平或垂直方向游动，写一个程序判断多少天后两只白天鹅才能够相会。

题解#

怎么说呢，本来和简单的一道题
结果因为一个知识点不熟
然后就没做出来
其实就是两遍DFS 第一遍求出每个点到他的最近的水的距离
然后一边dfs求出起点到终点的过程中的最小值

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
bool map[1505][1505];
int dis[1505][1505];
struct Point
{
    int x, y;
} S, E, Q[20000000];
int R, C;
int movex[5] = {0, 0, 0, 1, -1},
    movey[5] = {0, 1, -1, 0, 0};
bool flag[1505][1505];
void bfs_init()
{
    //memset(flag,0,sizeof(flag));
    int l = 1, r = 0;
    memset(dis, 0x3f, sizeof(dis));
    for (int i = 1; i <= R; i++)
    {
        for (int j = 1; j <= C; j++)
        {
            if (!map[i][j])
            {
                Q[++r] = (Point){i, j};
                dis[i][j] = 0;
            }
        }
    }
    while (l <= r)
    {
        Point k = Q[l++];
        for (int i = 1; i <= 4; i++)
        {
            if (k.x + movex[i] > R || k.x + movex[i] < 1)
                continue;
            if (k.y + movey[i] > C || k.y + movey[i] < 1)
                continue;
            if (dis[k.x + movex[i]][k.y + movey[i]] > dis[k.x][k.y] + 1)
            {
                dis[k.x + movex[i]][k.y + movey[i]] = dis[k.x][k.y] + 1;
                Q[++r] = (Point) { k.x + movex[i], k.y + movey[i] };
            }
        }
    }
}
int d[1505][1505];
 
int SPFA()
{
    memset(d, 0x3f, sizeof(d));
    d[S.x][S.y] = 0;
    int l = 1, r = 0;
    Q[++r] = S;
    //flag[S.x][S.y] = 1;
    while (l <= r)
    {
        Point k = Q[l++];
        //flag[k.x][k.y] = 0;
        for (int i = 1; i <= 4; i++)
        {
            if (k.x + movex[i] > R || k.x + movex[i] < 1)
                continue;
            if (k.y + movey[i] > C || k.y + movey[i] < 1)
                continue;
            if (d[k.x + movex[i]][k.y + movey[i]] > max(d[k.x][k.y], dis[k.x + movex[i]][k.y + movey[i]]))
            {
                d[k.x + movex[i]][k.y + movey[i]] = max(d[k.x][k.y], dis[k.x + movex[i]][k.y + movey[i]]);
                //if (!flag[k.x + movex[i]][k.y + movey[i]])
                //{
                    Q[++r] = (Point){k.x + movex[i], k.y + movey[i]};
                    //flag[k.x + movex[i]][k.y + movey[i]] = 1;
                //}
            }
        }
    }
    return d[E.x][E.y];
}
int main()
{
    //freopen("swan.in", "r", stdin);
    // freopen("swan.out", "w", stdout);
    char c;
    scanf("%d%d", &R, &C);
    bool flag = 0;
    for (int i = 1; i <= R; i++)
    {
        for (int j = 1; j <= C; j++)
        {
            c = getchar();
            while (c != '.' && c != 'X' && c != 'L')
                c = getchar();
            if (c == 'X')
                map[i][j] = 1;
            else if (c == 'L')
            {
                if (flag)
                    E = (Point){i, j};
                else
                {
                    S = (Point){i, j};
                    flag = 1;
                }
            }
        }
    }
    bfs_init();
    printf("%d", SPFA());
    //while (1)
    ;
}