P2130 题解
liangbowen
2022-07-08 14:58:46
## 前言
[题目传送门！](https://www.luogu.com.cn/problem/P2130)
[更好的阅读体验？](https://www.luogu.com.cn/blog/liangbowen/solution-p2130)
本题是练习 bfs 的好题。
## 思路
结合代码进行思路讲解。
首先是读入部分，我们可以用 `bool` 存下地图，节省空间开销。
需要注意，数据比较烂，**起始点可能有障碍**。
我们可以霸气地把起始点的障碍消掉。
```cpp
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 之前，我们准备一堆移动数组：
```cpp
//这些是用来记录答案的数组。
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()}$ 判断能否走动。
具体如下：
```cpp
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]$。
```cpp
//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$ 即可。
```cpp
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)$ 级别的。
## 完整代码
```cpp
#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;
}
```
希望能帮助到大家！