天鹅会面 - NekoMio's Blog

题目描述#

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

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

【输入格式】#

输入文件第一行包含两个用空格隔开的整数R和C，其中1 ≤ R, C ≤ 1500，接下来的R行每行包含C个字符，描述湖面的初始状态，‘·’表示水格，‘ X’表示冰格，‘ L’表示一只白天鹅。

【输出格式】#

输出文件仅一行包含一个整数表示两只白天鹅等到相邻那一天所需的天数。

【输入样例】#

8 17
…XXXXXX..XX.XXX
…XXXXXXXXX.XXX
…XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX…XXXX…
..XXXXX…XXX…
…XXXXX.XXXL…

【输出样例】#

2

Hint#

30%数据1 ≤ R《400.1 ≤ C《300
100%其中1 ≤ R, C ≤ 1500

题解#

怎么说呢，本来和简单的一道题
结果因为一个知识点不熟
然后就没做出来
其实就是两遍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)
    ;
}