[洛谷] P1141 01迷宫

1.题目

题目描述

有一个仅由数字$0$与$1$组成的$n\times n$格迷宫。若你位于一格$0$上，那么你可以移动到相邻$4$格中的某一格$1$上，同样若你位于一格$1$上，那么你可以移动到相邻$4$格中的某一格$0$上。

你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。

输入格式

第$1$行为两个正整数$n,m$。

下面$n$行，每行$n$个字符，字符只可能是$0$或者$1$，字符之间没有空格。

接下来$m$行，每行$2$个用空格分隔的正整数$i,j$，对应了迷宫中第$i$行第$j$列的一个格子，询问从这一格开始能移动到多少格。

输出格式

$m$行，对于每个询问输出相应答案。

样例输入 #1

2 2
01
10
1 1
2 2
1
2
3
4
5

样例输出 #1

4
4
1
2

提示

所有格子互相可达。

对于$20\%$的数据，$n\le 10$；

对于$40\%$的数据，$n\le 50$；

对于$50\%$的数据，$m\le 5$；

对于$60\%$的数据，$n\le 100,m\le 100$；

对于$100\%$的数据，$n\le 1000,m\le 100000$。

2.分析

记忆化搜索~

3.代码

1.dfs 70 TLE

#include 
using namespace std;
const int N = 1e3 + 10;
#include  //memset !
char g[N][N];
bool st[N][N];
int n, q;
int cnt;
//最长路径
void dfs(int x, int y)
{
	//visited
	if (st[x][y])
		return;
	//否则
	++cnt;
	st[x][y] = true;
	int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };
	for (int i = 0; i < 4; ++i)
	{
		int a = x + dx[i], b = y + dy[i];
		if (a >= 1 && a <= n && b >= 1 && b <= n && (g[x][y] == '0' && g[a][b] == '1' || g[x][y] == '1' && g[a][b] == '0'))
			dfs(a, b);
	}
}

int main()
{

	scanf("%d%d", &n, &q);
	getchar(); //吞\n
	for (int i = 1; i <= n; ++i)
		scanf("%s", g[i] + 1);
	while (q--)
	{
		//init
		memset(st, 0, sizeof st);
		cnt = 0;
		int x, y;
		scanf("%d%d", &x, &y);
		dfs(x, y);
		printf("%d\n", cnt);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

2.dfs + 记忆搜索过的点[连通块] 90 TLE

由于在搜索某条路径时，包含了很多点，则将这些点均赋值为最终路径长度，避免重复搜索

#include 
using namespace std;
const int N = 1e3 + 10;
#include  //memset !
#include   //记录路径
typedef pair<int, int> PII;
set<PII>SP;

char g[N][N];
bool st[N][N];
int d[N][N];
int n, q;
int cnt;
//最长路径
void dfs(int x, int y)
{
	//visited
	if (st[x][y])
		return;
	//否则
	++cnt;
	st[x][y] = true;
	SP.insert({x,y});  //记录路径
	int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };
	for (int i = 0; i < 4; ++i)
	{
		int a = x + dx[i], b = y + dy[i];
		if (a >= 1 && a <= n && b >= 1 && b <= n && (g[x][y] == '0' && g[a][b] == '1' || g[x][y] == '1' && g[a][b] == '0'))
			dfs(a, b);
	}
}

int main()
{
	scanf("%d%d", &n, &q);
	getchar(); //吞\n
	for (int i = 1; i <= n; ++i)
		scanf("%s", g[i] + 1);

	while (q--)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		if (d[x][y]) {
			printf("%d\n", d[x][y]);
		}
		else
		{
			//init
			memset(st, 0, sizeof st);
			SP.clear();  //清空路径记录
			cnt = 0;
			dfs(x, y);

			for (auto x : SP)
			{
				int a = x.first, b = x.second;
				d[a][b] = cnt;
			}

			printf("%d\n", cnt);
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

试了一下，吸氧优化后还是通过不了，第二个测试点太毒瘤了

3.dfs + 连通块染色思想 (对2.的优化) AC

可以将不同的连通块染成不同的颜色，即做不同的标记，给每个标记赋上不同的值即可

//dfs+染色
#include 
using namespace std;
#include 
const int N = 1e3 + 10;
const int M = 1e5 + 10;

int cr[M];  //记录每个颜色所对应的答案
char g[N][N]; //迷宫
int d[N][N]; //标记连通块 并 染色
int n, m;

void dfs(int x, int y, int fg, int col)
{
	//base case 已经写到 for循环中

	d[x][y] = col;  //标记为 col
	cr[col]++;  //标记为col的路径长度+1
	int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };
	for (int i = 0; i < 4; ++i)
	{
		int a = x + dx[i], b = y + dy[i];
		if (a >= 1 && a <= n && b >= 1 && b <= n && d[a][b] == -1 && g[a][b]-'0'==!fg)
			dfs(a, b, !fg, col);
	}
}

int main()
{
	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; ++i)
		scanf("%s", g[i] + 1);

	memset(d, -1, sizeof d);

	for (int i = 0; i < m; ++i)
	{
		int x, y;
		scanf("%d%d", &x, &y);

		if (d[x][y] == -1)//未遍历
			dfs(x, y, g[x][y] - '0', i);
		printf("%d\n", cr[d[x][y]]);
	}

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

4.bfs + 染色 AC

#include 
using namespace std;
#include 
#include  //memset

const int N = 1e3 + 10, M = 1e5 + 10;
typedef pair<int, int> PII;
queue<PII> q;
char g[N][N];  //迷宫
int d[N][N];  //搜索
int col[M];
int n, m;
int k;   //连通图标记

void bfs(int x, int y)
{
	//init
	d[x][y] = k;
	col[k]++;
	q.push({ x,y });

	int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };
	while (q.size())
	{
		//取队头
		auto t = q.front();
		q.pop();
		for (int i = 0; i < 4; ++i)
		{
			int a = t.first + dx[i], b = t.second + dy[i];
			if (a >= 1 && a <= n && b >= 1 && b <= n && d[a][b] == -1 && (g[t.first][t.second] ^ 48) + (g[a][b] ^ 48) == 1)
			{
				d[a][b] = k;
				col[k]++;
				q.push({ a,b });
			}
		}
	}
}

int main()
{
	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; ++i)
		scanf("%s", g[i] + 1);

	//init dist
	memset(d, -1, sizeof d);

	for (int i = 0; i < m; ++i)
	{
		int x, y;
		scanf("%d%d", &x, &y);

		if (d[x][y] == -1)
		{
			//new 连通块
			k++;
			bfs(x, y);
		}
		printf("%d\n", col[d[x][y]]);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

dfs的优势在于所占内存较少，速度上比bfs慢些~

4.总结

bfs 、 dfs 、染色~

5.更新日志

2022.8.27 整理

欢迎交流、讨论、指正~
不正确、不理解之处欢迎评论留言~