HDU 4775 Infinite Go（暴力模拟+BFS）

超、凢脫俗 2022-06-09 06:17 143阅读 0赞

Go is a proverbial board game originated in China. It has been proved to be the most difficult board game in the world. “The rules of Go are so elegant, organic, and rigorously logical that if intelligent life forms exist elsewhere in the universe, they almost certainly play Go.” said Emanuel Lasker, a famous chess master.  
　　A Go board consists of 19 horizontal lines and 19 vertical lines. So there are 361 cross points. At the beginning, all cross points are vacant.  
　　Go is played by two players. The basic rules are:  
　　1. One player owns black stones and the other owns white stones.  
　　2. Players place one of his stones on any vacant cross points of the board alternately. The player owns black stones moves first.  
　　3. Vertically and horizontally adjacent stones of the same color form a chain.  
　　4. The number of vacant points adjacent (vertically or horizontally) to a chain is called the liberty of this chain. Once the chain has no liberty, it will be captured and removed from the board.  
　　5. While a player place a new stone such that its chain immediately has no liberty, this chain will be captured at once unless this action will also capture one or more enemy’s chains. In that case, the enemy’s chains are captured, and this chain is not captured.  
　　  
　　In effect, Go also has many advanced and complex rules. However, we only use these basic rules mentioned above in this problem.  
　　Now we are going to deal with another game which is quite similar to Go. We call it “Infinite Go”. The only difference is that the size of the board is no longer 19 times 19 -- it becomes infinite. The rows are numbered 1, 2, 3, ..., from top to down, and columns are numbered 1, 2, 3, ..., from left to right. Notice that the board has neither row 0 nor column 0, which means even though the board is infinite, it has boundaries on the top and on the left.  
　　In this problem, we are solving the problem that, given the actions of two players in a set of Infinite Go, find out the number of remaining stones of each player on the final board.

Input

The input begins with a line containing an integer T (1 <= T <= 20), the number of test cases.  
　　For each test case, the first line contains a single integer N (1 <= N <= 10000), the number of stones placed during this set. Then follows N lines, the i-th line contains two integer X and Y (1 <= X, Y <= 2,000,000,000), indicates that the i-th stone was put on row X and column Y (i starts from 1). The stones are given in chronological order, and it is obvious that odd-numbered stones are black and even-numbered ones are white.

Output

For each test case, output two integers Nb and Nw in one line, separated by a single space. Nb is the number of black stones left on the board, while Nw is the number of white stones left on the board.

Sample Input

1
    7
    5 5
    4 5
    3 5
    3 4
    4 4
    3 3
    4 6

Sample Output

4 2

题解：  
题意：  
就是下围棋，有黑棋和白棋，输入n表示下了n步，奇数行步数为黑棋下的坐标（随便），偶数步数为白棋下的坐标，问你最后黑白棋分别有几颗  
思路：

我们知道当一堆同色被一堆异色棋子或者边界围住了而且没有缝隙，这一堆棋子就会被吃掉，那么我们就用bfs来模拟这一个过程，每下一个子，我们先在图上下好它，然后搜索周围的四个格子，如果格子上有棋子，那么就搜索该棋子的四周，只要四周发现了一个空地（没有棋子）的地方就说明这一堆不可能被吃掉，就不用搜了，如果搜到了同色，那么就加入队列继续搜索，如果搜到了异色和边界就跳掉，最后如果都没返回的话说明被包围了，把连通的同种颜色删掉就好了。。一开始还以为会tle，结果发现我的写法居然还是几个ac里面最快的几个，还有要注意的是数据很大开二维数组判断是否遍历过会炸，所以要用map

ps:

不要害怕虽然代码很长但是思路清晰的话很简单，我居然是第一个a的hhhhhh

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    using namespace std;
    #define INF 100861111
    #define ll long long
    #define eps 1e-15
    map<pair<int,int>,int>M,vis;
    int num1,num2;
    int dirx[4]={0,0,-1,1};
    int diry[4]={1,-1,0,0};
    int bfs(int x,int y,int d)
    {
        int i,j;
        vis.clear();
        pair<int,int>a=make_pair(x,y);
        vis[a]=1;
        int xx,yy;
        queue<pair<int,int> >q;
        q.push(a);
        while(!q.empty())
        {
            a=q.front();
            q.pop();
            for(i=0;i<4;i++)
            {
                xx=a.first+dirx[i];
                yy=a.second+diry[i];
                pair<int,int>t=make_pair(xx,yy);
                if(xx<=0||yy<=0||vis[t])
                {
                    continue;
                }
                vis[t]=1;
                if(M[t]==0)
                    return 1;
                if(d==0)
                {
                    if(M[t]==1)
                    {
                         q.push(t);
                    }
                }
                else
                {
                    if(M[t]==-1)
                    {
                        q.push(t);
                    }
                }
            }
        }
        return 0;
    }
    void des(int x,int y,int d)//这里是删去一片连通的棋子，复制上面的稍作修改就好了
    {
        int i,xx,yy;
        pair<int,int>a=make_pair(x,y);
        queue<pair<int,int> >q;
        q.push(a);
        while(!q.empty())
        {
            a=q.front();
            M[a]=0;
            d?num2--:num1--;
            q.pop();
            for(i=0;i<4;i++)
            {
                xx=a.first+dirx[i];
                yy=a.second+diry[i];
                pair<int,int>t=make_pair(xx,yy);
                if(xx<=0||yy<=0)
                {
                    continue;
                }
                if(d==0)
                {
                    if(M[t]==1)
                    {
                         q.push(t);
                    }
                }
                else
                {
                    if(M[t]==-1)
                    {
                        q.push(t);
                    }
                }
            }
        }
    }
    int main()
    {
        int i,j,test,n,xx,yy;
        int x,y;
        scanf("%d",&test);
        while(test--)
        {
            scanf("%d",&n);
            M.clear();
            num1=0;
            num2=0;
            for(i=0;i<n;i++)
            {
                scanf("%d%d",&x,&y);
                pair<int,int>t=make_pair(x,y);
                M[t]=i%2?-1:1;//黑棋用1，白棋用-1
                i%2?num2++:num1++;
                for(j=0;j<4;j++)
                {
                    xx=x+dirx[j];
                    yy=y+diry[j];
                    t=make_pair(xx,yy);
                    if(x<=0||y<=0||M[t]==0)
                        continue;
                    int d=M[t]==1?0:1;
                    if(!bfs(xx,yy,d))
                    {
                        des(xx,yy,d);
                    }
                }
                t=make_pair(x,y);
                int d=M[t]==1?0:1;
                if(!bfs(x,y,d))//最后再判断自己
                {
                    des(x,y,d);
                }
            }
            printf("%d %d\n",num1,num2);
        }
        return 0;
    }