洛谷 P1141 01迷宫

BFS或者并查集

题目描述

有一个仅由数字0与1组成的n×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

4
4

说明/提示

对于100%的数据，n≤1000,m≤100000

对于输入一组，bfs一遍，代码我放在下面：（只能过70%）

#include <iostream>
#include <queue>
using namespace std;
const int N = 1005;

int direct[4][2] = {{0,1},{-1,0},{0,-1},{1,0}};//方向
bool flag[N][N]={false};
char chart[N][N];

typedef struct{
	int x, y;
}Node;
int n, m;

void init() {
	for ( int i = 1; i <= n; ++i ) {
		for ( int j  = 1; j <= n; ++j )
			flag[i][j] = false;
	}
}

void bfs(Node k)
{
	int ans = 1;
	flag[k.x][k.y] = true;
	queue<Node> q;
	q.push(k);
	while ( !q.empty() ) {
		Node top = q.front();
		q.pop();
	
		for ( int i = 0; i < 4; ++i ) {
			int tx = top.x + direct[i][0];
			int ty = top.y + direct[i][1];
			//满足条件
			if ( tx >= 1 && tx <= n && ty >= 1 && ty <= n
				&& !flag[tx][ty] )
			{
				if ( chart[top.x][top.y] == '0' && chart[tx][ty] == '1'
				  || chart[top.x][top.y] == '1' && chart[tx][ty] == '0'
				)
				{
					Node temp = {tx,ty};
					q.push(temp);
					flag[tx][ty] = true;
					ans++;
				}
			}
		}
	}
	cout << ans <<endl;
}

int main()
{
	cin >> n >> m;
	
	for ( int i = 1; i <= n; ++i ) {
		for ( int j = 1; j <= n; ++j ) {
			cin >> chart[i][j];
		}
	}
	while (m--) {
		int x, y;
		cin >> x >> y;
		Node now = {x,y};
		bfs(now);
		init();
	}
	
	return 0;
}

其实没有必要重复bfs，是吧，因为从一个点只要能到的那一片，这一片的这些点的结果都是一样的。

就是一片连通的点就是一个集合（很容易想到并查集，我这里先不说并查集，用这样一个思想来做一遍）

看下面的帮助理解：

假如样例是这样的：

4 4
0101
1000
1000
1000
1 1
4 4
2 2
1 3
    
(1,1)(4,4)这个点可以到达的方格(用#和@标记出来了)
####
##00
1000
100@

(1,1)是我们输入的第1个点，所以#的方格的父亲就标记为1
(1,1)最开始没有父亲，bfs一遍，把它能到的点，都给标记上父亲1
father[1][1] = father[1][2] = father[1][3] =
father[1][4] = father[2][1] = father[2][2] = 1;
在bfs最后，dis[1] = 6（ans）;
    
(4,4)是我们输入的第2个点，所以@的方格的父亲就标记为2
father[4][4] = 2;
在bfs最后，dis[2]= 1（ans）;

(2,2)发现他有父亲，直接输出父亲的结果，dis[father[2][2]] = dis[1] = 6;
(1,3)发现他有父亲，直接输出父亲的结果，dis[father[1][3]] = dis[1] = 6;

这样，当我们输入一个集合里面的点来查询的时候，我们只需要
看看有没有父亲，如果有，就直接输出父亲的结果；没有就bfs。
这样就节省了很多时间。

要点：（每个集合我们定义一个父亲，父亲和所有孩子的结果是一样的）

• father[i] [j]数组的值表示（i, j）这个点的父亲。什么意思呢？father[2] [2] = 1，意思就是（2,2）这个点他的父亲是我们输入的第一个点。

• father[i] [j] = k, 表示（i，j）这个点的结果跟我们输入的第k个点的结果是一样的

• dis[i] 数组表示 我们输入的 第 i 个点可以到达的方格数。

#include <iostream>
#include <queue>
using namespace std;
const int N = 1005;
const int M = 1e5+5;

int direct[4][2] = {{0,1},{-1,0},{0,-1},{1,0}};//方向
int father[N][N]={0}, dis[M];
bool flag[N][N]={false}; //访问标记
char chart[N][N]; //存二维字符数组

typedef struct{
	int x, y;
}Node;//定义点
int n, m;

//now_m表示当前集合的  父亲点
void bfs(Node k, int now_m)
{
	father[k.x][k.y] = now_m;
	
	int ans = 1;
	flag[k.x][k.y] = true;
	queue<Node> q;
	q.push(k);
	while ( !q.empty() ) {
		Node top = q.front();
		q.pop();
	
		for ( int i = 0; i < 4; ++i ) {
			int tx = top.x + direct[i][0];
			int ty = top.y + direct[i][1];
			//满足条件
			if ( tx >= 1 && tx <= n && ty >= 1 && ty <= n
				&& !flag[tx][ty] )
			{
				if ( chart[top.x][top.y] == '0' && chart[tx][ty] == '1'
				  || chart[top.x][top.y] == '1' && chart[tx][ty] == '0'
				)
				{
					Node temp = {tx,ty};
					q.push(temp);
					flag[tx][ty] = true;
					father[tx][ty] = now_m;//当前点的父亲标记为now_m
					ans++;
				}
			}
		}
	}
    //当前集合父亲点能够到达的方格数
	dis[now_m] = ans;
}

int main()
{
	cin >> n >> m;
	
	for ( int i = 1; i <= n; ++i ) {
		for ( int j = 1; j <= n; ++j ) {
			cin >> chart[i][j];
		}
	}
	for ( int i = 1; i <= m; ++i ) {
		int x, y;
		cin >> x >> y;
		Node node = {x,y};
        //没父亲
		if ( father[x][y] == 0 ) {
			bfs(node,i);
		}
        //有父亲，结果就等于父亲的结果
		else {
			dis[i] = dis[father[x][y]];//结果就是他的父亲的结果
		}
	}
	for ( int i = 1; i <= m; ++i ) {
		cout << dis[i] << '\n';
	}
		
	return 0;
}