题目https://www.luogu.org/problemnew/show/p1141
这个题解主要针对我个人出现的一些问题和注意的地方。
解题思路
首先说一下联通块
联通块这个比较抽象，举个例子就是假设一条鱼在一个池塘里游泳，那么在时间不限的情况下，小鱼会游过池塘的所有位置，而这个与小鱼的出发点是无关的。
所以在本题中，假设从一个坐标开始，对他能经过的所有点进行标记，那么在剩下的询问中，如果询问的坐标已经被标记，那么它所经过的点与假设的坐标是相同的，所以就可以创建一个统计格子数目的数组cnt和一个联通图int数组_map与迷宫的坐标一一对应，假设第i次询问可以经过n个点，那么就把这个联通图所有经过的点赋值为i，并赋值cnt[i]=经过的格子数。在剩下的询问中，如果已经被标记，则直接输出_map对应的i所对应的cnt数组的值。
我本人出现的错误（一直不知道哪里错了，看了很长时间才反应过来）
一开始并没有使用_map作为联通图，而是直接在原迷宫内修改，但是在询问过多的情况下，两位数的值就不能赋值在一个位置中（当时不知道为什么这么写，有点懵），所以在情况超过9次之后就会出错。具体怎么个情况就是代码中注释的部分。
说明：
我的bfs可能比较复杂，个人习惯，但是觉得理解起来还是比较方便。
完整代码
#include <iostream> #include<deque> #include<queue> #include<stdio.h> #define check(x, y) (x<wx && x>=0 && y >=0 && y<hy) using namespace std; int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; char room[1001][1001]; int wx,hy,num,cnt[1000001],way; int _map[1001][1001]; struct node {int x,y;}; int bfs(int dx,int dy) { num=1; queue<node> q; node start,next; start.x=dx; start.y=dy; q.push(start); while(!q.empty()) { start=q.front(); q.pop(); if(room[start.x][start.y]=='1'||room[start.x][start.y]=='#') { //room[start.x][start.y]='0'+way; room[start.x][start.y]='*'; _map[start.x][start.y]=way; for(int i=0;i<4;i++) { next.x=start.x+dir[i][0]; next.y=start.y+dir[i][1]; //cout<<next.x<<" "<<next.y<<endl; if(check(next.x,next.y)&&room[next.x][next.y]=='0') { num++; room[next.x][next.y]='.'; q.push(next); } } } else if(room[start.x][start.y]=='0'||room[start.x][start.y]=='.') { //room[start.x][start.y]='0'+way; room[start.x][start.y]='*'; _map[start.x][start.y]=way; for(int i=0;i<4;i++) { next.x=start.x+dir[i][0]; next.y=start.y+dir[i][1]; //cout<<next.x<<" "<<next.y<<endl; if(check(next.x,next.y)&&room[next.x][next.y]=='1') { num++; room[next.x][next.y]='#'; q.push(next); } } } //cout<<"size="<<q.size()<<" "<<num<<endl; } return num; } int main() { int n,m,dx,dy; cin>>n>>m; wx=hy=n; for(int i=0;i<n;i++) cin>>room[i]; for(way=2;way<=m+1;way++) { cin>>dx>>dy; dx=dx-1; dy=dy-1; if(room[dx][dy]=='0'||room[dx][dy]=='1') cnt[way]=bfs(dx,dy); //cout<<cnt[room[dx][dy]-'0']; printf("%dn",cnt[_map[dx][dy]]); //for(int i=0;i<n;i++) //cout<<room[i]<<endl; } return 0; }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/604768.html