P2130 题解

前言

题目传送门！

更好的阅读体验？

本题是练习 bfs 的好题。

思路

结合代码进行思路讲解。

首先是读入部分，我们可以用 bool 存下地图，节省空间开销。

需要注意，数据比较烂，起始点可能有障碍。

我们可以霸气地把起始点的障碍消掉。

const int N = 1005;
bool a[N][N];
int n, m, fx, fy;
void Input() //简单的输入。我们可以用 bool 存地图，减少空间开销。 
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            char x;
            cin >> x;
            if (x == '$' || x == '.') a[i][j] = true;
            if (x == 'X') a[i][j] = false;
            if (x == '#') fx = i, fy = j, a[i][j] = true;
        }
    a[1][1] = true; //本题数据很烂，(1,1) 可能有障碍，需要手动消除。 
}

然后就是 bfs 了。在 bfs 之前，我们准备一堆移动数组：

//这些是用来记录答案的数组。 
struct Node {int x, y;};
int ans[N][N];
bool vis[N][N];

//下面这个，是记录步数的表格（个人习惯下标从 1 开始）。
int foot[15] = {0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024};
//下面这个，是上下左右的方位数组（个人习惯下标从 1 开始）。
int dict[5][2] = {{0, 0}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}}; 

本题最特殊的地方在于，每一步走动之间不能有障碍。这是显然的事情。

因此，我们可以在 bfs 中用函数 \texttt{run()} 判断能否走动。

具体如下：

int bfs() //基本上和 bfs 的模版区别不大。
{
    queue <Node> Q;
    ans[1][1] = 0, vis[1][1] = true;
    Q.push( (Node){1, 1} );
    while (!Q.empty())
    {
        int x = Q.front().x, y = Q.front().y;
        //cout << "x = " << x << ", y = " << y << ".\n";
        if (x == fx && y == fy) return ans[x][y];
        Q.pop();
        for (int i = 1; i <= 4; i++)
            for (int j = 1; j <= 10; j++)
            {
                //以下稍微有点特殊。
                int dx = x + dict[i][0] * foot[j], dy = y + dict[i][1] * foot[j];
                if (dx < 1 || dx > n || dy < 1 || dy > m) continue;
                if (!run(x, y, dx, dy) || vis[dx][dy]) continue;
                ans[dx][dy] = ans[x][y] + 1, vis[dx][dy] = true;
                Q.push( (Node){dx, dy} );
            }
    }
    return -1;
}

观察这份代码，容易发现，时间复杂度 O(n\times m \times\log n) 加上 \texttt{run()} 的时间复杂度。

如果 \texttt{run()} 仍然暴力枚举，时间复杂度将会是 O(n\times m \times\log^2 n)，极大可能超时。

因此，我们试图让 \texttt{run()} 函数 O(1) 计算。

事实上，我们可以前缀和优化它。

具体地，设 sum_{i, j} 表示 (1,1) 到 (i,j) 的矩阵中，不可以走的点的个数。

这个就是典型的二维前缀和：sum_{i, j} = sum_{i-1,j} + sum_{i, j-1} - sum_{i-1,j-1} + [a_{i,j} = false]。

//sum[i][j] 表示 (1,1) 到 (i,j) 的矩阵中，不可以走的点的个数。 
int sum[N][N];
void init() //预处理前缀和。 
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + (a[i][j] == false);
    //for(int i=1;i<=n;i++,cout<<'\n')for(int j=1;j<=m;j++)cout<<sum[i][j]<<' ';
}

那么，\texttt{run()} 只需要让 (x1,y1) 到 (x2,y2) 的矩阵中，无法走的点的数量为 0 即可。

bool run(int x1, int y1, int x2, int y2) //判断能否从 (x1,y1) 到 (x2,y2)。 
{
    if (x1 > x2 || y1 > y2) swap(x1, x2), swap(y1, y2);
    int s = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
    return (s == 0);
}

至此，本题结束。时间复杂度上文已经提到，是 O(n^2 \log n) 级别的。

完整代码

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
void Fastio()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);    
}
const int N = 1005;
bool a[N][N];
int n, m, fx, fy;
void Input() //简单的输入。我们可以用 bool 存地图，减少空间开销。 
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            char x;
            cin >> x;
            if (x == '$' || x == '.') a[i][j] = true;
            if (x == 'X') a[i][j] = false;
            if (x == '#') fx = i, fy = j, a[i][j] = true;
        }
    a[1][1] = true; //本题数据很烂，(1,1) 可能有障碍，需要手动消除。 
}

//sum[i][j] 表示 (1,1) 到 (i,j) 的矩阵中，不可以走的点的个数。 
int sum[N][N];
void init() //预处理前缀和。 
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + (a[i][j] == false);
    //for(int i=1;i<=n;i++,cout<<'\n')for(int j=1;j<=m;j++)cout<<sum[i][j]<<' ';
}

bool run(int x1, int y1, int x2, int y2) //判断能否从 (x1,y1) 到 (x2,y2)。 
{
    if (x1 > x2 || y1 > y2) swap(x1, x2), swap(y1, y2);
    int s = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
    return (s == 0);
}

//这些是用来记录答案的数组。 
struct Node {int x, y;};
int ans[N][N];
bool vis[N][N];

//下面这个，是记录步数的表格（个人习惯下标从 1 开始）。
int foot[15] = {0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024};
//下面这个，是上下左右的方位数组（个人习惯下标从 1 开始）。
int dict[5][2] = {{0, 0}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}}; 

int bfs()
{
    queue <Node> Q;
    ans[1][1] = 0, vis[1][1] = true;
    Q.push( (Node){1, 1} );
    while (!Q.empty())
    {
        int x = Q.front().x, y = Q.front().y;
        //cout << "x = " << x << ", y = " << y << ".\n";
        if (x == fx && y == fy) return ans[x][y];
        Q.pop();
        for (int i = 1; i <= 4; i++)
            for (int j = 1; j <= 10; j++)
            {
                //以下稍微有点特殊。
                int dx = x + dict[i][0] * foot[j], dy = y + dict[i][1] * foot[j];
                if (dx < 1 || dx > n || dy < 1 || dy > m) continue;
                if (!run(x, y, dx, dy) || vis[dx][dy]) continue;
                ans[dx][dy] = ans[x][y] + 1, vis[dx][dy] = true;
                Q.push( (Node){dx, dy} );
            }
    }
    return -1;
}
int main()
{
    Fastio();
    Input();
    init();
    cout << bfs();
    return 0;
}

希望能帮助到大家！