洛谷 P1141 01迷宫

洛谷 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;
}
上一篇:五(二)、spring 声明式事务xml配置


下一篇:使用51单片机与esp8266通信过程中串口助手和网络调试助手建立透传的解决方案