subject https://www.luogu.org/problemnew/show/P1141

This solution is mainly for my personal problems and attention.

Solving problems

Let's start with the Unicom block

For example, if a fish swims in a pond, then in the case of unlimited time, the small fish will swim across all positions of the pond, which has nothing to do with the starting point of the small fish.

So in this problem, if we start from a coordinate and mark all the points that he can pass through, then in the rest of the query, if the coordinates of the query have been marked, then the points that it passes through are the same as the assumed coordinates, so we can create an array of statistical lattice sub numbers cnt and an array of interconnection graphs int map, which correspond to the coordinates of the maze one by one. Suppose that No If I query can pass through n points, then I will assign all the passing points of this connection graph as I, and cnt[i] = the number of cells passed. In the rest of the query, if it has been marked, the value of the cnt array corresponding to the I corresponding to the map will be output directly.

My own mistake (I don't know what's wrong all the time, I read it for a long time before I react)

At the beginning, it did not use ﹣ map as the connection diagram, but directly modified in the original maze. However, in the case of too many queries, the value of two digits cannot be assigned in one position (at that time, I didn't know why it was written, which was a bit muddled). Therefore, after more than 9 times, an error will occur. The specific situation is the comment part of the code.

Explain:

My bfs may be complex and personal, but I think it's more convenient to understand.

Complete code

#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("%d\n",cnt[_map[dx][dy]]);
    //for(int i=0;i<n;i++)
        //cout<<room[i]<<endl;
}
    return 0;
}