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;
}

希望能帮助到大家！
首发：2022-07-08 14:58:46