洛谷P1141 01迷宫【bfs】

题目链接https://www.luogu.org/problemnew/show/P1141

题意:

有一个填了0和1的n*n的格子,只能0走到1,1走到0

有m组询问(数据量是1e5),问某一个格子可以到达的格子数。

思路:

刚开始一直在想记忆化搜索。某一个格子走过了之后的格子数记下来,之后访问到的时候加上。

但是这样会重复的。比如(x,y)走到(i,j),他们能走到的格子是有交集的,并不是包含的关系。

应该要想到 连通块。

给定的这个图形成了若干的连通块。我们只需要预处理一下这些连通块,对于每次询问查询他对应的连通块的大小就行了。

 #include<stdio.h>
#include<stdlib.h>
#include<map>
#include<set>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue> using namespace std;
typedef pair<int, int> pr; int n, m;
int mat[][];
int dx[] = {, -, , };
int dy[] = {, , , -}; int id[][];
int cnt[]; bool check(pr p)
{
int i = p.first, j = p.second;
return (i > && i <= n && j > && j <= n);
} void bfs(int i, int j, int k)
{
int c = ;
queue<pr>que;
pr st = make_pair(i, j);
que.push(st);
id[i][j] = k;
while(!que.empty()){
pr now = que.front();que.pop();
for(int i = ; i < ; i++){
pr tmp = make_pair(now.first + dx[i], now.second + dy[i]);
if(check(tmp) && !id[tmp.first][tmp.second] && mat[tmp.first][tmp.second] ^ mat[now.first][now.second]){
id[tmp.first][tmp.second] = k;
que.push(tmp);
c++;
}
}
}
cnt[k] = c;
} int main()
{
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++){
char s[];
scanf("%s", s);
for(int j = ; j <= n; j++){
mat[i][j] = s[j - ] - '';
}
}
int now_id = ;
for(int i = ; i <= n; i++){
for(int j = ; j <= n; j++){
if(!id[i][j]){
bfs(i, j, now_id);
now_id++;
}
}
} for(int i = ; i < m; i++){
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", cnt[id[x][y]]);
} return ;
}
上一篇:[Immutable.js] Working with Subsets of an Immutable.js Map()


下一篇:[Immutable.js] Differences between the Immutable.js Map() and List()