列表

详情

NC221780. BetaGo

描述

Go is a traditional board game for two players invented in China more than 2500 years ago. In this game, the aim is to surround more territory than the opponent. 

The two players, Black and White, take turns placing stones of their color on the intersections of the board, one stone at a time. The board size is a  grid. In the beginning, the board is empty. Black plays first. The players may choose any unoccupied intersection to play on, except for those forbidden by the suicide rules (see below). Once played, a stone can never be moved. A player may also pass, declining to place a stone. When both players pass consecutively, the game ends and is then scored.

Liberties: Vertically and horizontally adjacent stones of the same color form a group, a discrete unit that cannot then be divided. Notice that only stones connected to one another by the lines on the board create a group, but stones that are diagonally adjacent are not connected. A vacant point adjacent to a stone, along one of the grid lines of the board, is called a liberty for that stone. Stones in a group share their liberties. A group of stones must have at least one liberty to remain on the board. When a group is surrounded by opposing stones so that it has no liberties, it is captured and removed from the board.
There are one black group and two white groups in the picture below, with their liberties marked with dots. Liberties are shared among all stones of a group and can be counted. Here the black group has liberties, while the two white groups have liberties each.



Capture: In the picture below, the black group has only one liberty. If White plays at the black dot, the two black stones will be removed from the board, which is called capture.



Suicide Rule: A player may not place a stone such that it or its group immediately has no liberties, unless doing so immediately captures an enemy group of its final liberty. In the latter case, the enemy group is captured, leaving the new stone with at least one liberty.
In the picture below, if White plays a stone at the black dot, which has no liberty either, the two black stones will be immediately removed from the board, and then the stone White just placed has one liberty.



However, in the picture below, White can not play a stone at either of the two black dots. Because the stone White places has no liberty, and the black group has one liberty left.


Beta Go is a computer program that plays the board game Go very well, and it has defeated many professional human Go players. Moca loves playing the board game, and Go is her favorite. One day, Moca is playing Go with Beta Go online. Of course, she never wins Beta Go, which makes her very angry. As a result, after Beta Go placing several stones on the board, Moca hacks into the game system to stop Beta Go from playing and removes the stones she placed on the board. Now, the only stones left on the board are the ones Beta Go played, and Moca continues to place her stones on the board, while Beta Go can only choose to pass its turn. 

Your task is to help Moca capture the maximum number of stones that Beta Go played. Notice that you can not break the rules mentioned above, and you can not move the stones Beta Go played except capturing.

输入描述

The first line contains one integer   -- the size of the board.

The next  lines describe the game board. Each of the following  lines contains  characters "." or "O". If a character equals ".", the corresponding intersection is empty. If it equals "O", the corresponding cell is a stone Beta Go played.

It is guaranteed that there exists at least one empty cell.

输出描述

Print one integer -- the maximum number of stones captured.

示例1

输入: 

7
..O.O..
.O.OOOO
..O....
...OOOO
.......
.......
.......

输出: 

12

示例2

输入: 

5
.O.O.
.OOOO
.....
....O
.....

输出: 

1

说明:

In the first example, assume that Beta Go plays black stones. The initial game board is as below.



In the beginning, you can not capture the upper right black group, but you can capture these three black stones in the next three pictures in order.





Now, you can easily capture the last two black groups. Finally, you can capture all  stones that Beta Go played.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 1234ms, 内存消耗: 355300K, 提交时间: 2023-03-04 14:57:13 

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef pair<int,int> pii;
const int N = 1e3+10, inf = 0x3f3f3f3f, mod = 1e9+7;

struct node{
    int x,y;
};

int n,cnt=0;
char maze[N][N];
int sum[N*N],num[N*N];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int vis[N][N];
map<pii,int>ma;
vector<int>g[N*N];
unordered_map<int,int>m[N*N];
int ind[N*N],outd[N*N],in[N*N];
int type[N*N];

bool check(int x)
{
    if(type[x]==0) return ind[x]<outd[x];
    else return ind[x]<=1;
}

void bfs1(int x,int y,int v)
{
    queue<node>q;
    q.push({x,y});
    vis[x][y]=v;
    while(!q.empty())
    {
        auto now=q.front();
        q.pop();
        sum[v]++;
        for(int i=0;i<4;i++)
        {
            auto ne=now;
            ne.x+=dx[i];
            ne.y+=dy[i];
            if(ne.x<1||ne.y<1||ne.x>n||ne.y>n||maze[ne.x][ne.y]=='O') continue;
            if(vis[ne.x][ne.y]) continue;
            q.push({ne.x,ne.y});
            vis[ne.x][ne.y]=v;
        }
    }
}

void bfs2(int x,int y,int v)
{
    queue<node>q;
    q.push({x,y});
    vis[x][y]=v;
    while(!q.empty())
    {
        auto now=q.front();
        q.pop();
        sum[v]++;
        for(int i=0;i<4;i++)
        {
            auto ne=now;
            ne.x+=dx[i];
            ne.y+=dy[i];
            if(ne.x<1||ne.y<1||ne.x>n||ne.y>n||maze[ne.x][ne.y]=='.') continue;
            if(vis[ne.x][ne.y]==v) continue;
            q.push({ne.x,ne.y});
            vis[ne.x][ne.y]=v;
        }
    }
}

void solve()
{
    
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>maze[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(maze[i][j]=='.'&&!vis[i][j])
            {
                bfs1(i,j,++cnt);
                type[cnt]=0;
            }
            else if(maze[i][j]=='O'&&!vis[i][j])
            {
                bfs2(i,j,++cnt);
                type[cnt]=1;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            set<int>s;
            for(int k=0;k<4;k++)
            {
                int tx=i+dx[k],ty=j+dy[k];
                if(tx>=1&&ty>=1&&tx<=n&&ty<=n)
                {
                    if(vis[tx][ty]!=vis[i][j])
                    {
                        s.insert(vis[tx][ty]);
                    }
                }
            }
            for(auto t:s)
            {
                m[t][vis[i][j]]++;
            }
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        if(type[i]==0)
        {
            for(auto [k,v]:m[i]) g[k].push_back(i),ind[i]++;
        }
        else
        {
            for(auto [k,v]:m[i])
            {
                if(v!=sum[k]) continue;
                g[k].push_back(i),ind[i]++;
            }
        }
    }
    
    for(int i=1;i<=cnt;i++)
    {
        outd[i]=ind[i];
    }
    queue<int>q;
    for(int i=1;i<=cnt;i++)
    {
        if(check(i)) q.push(i),in[i]=1;
    }
    int ans=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        if(type[u]==1) ans+=sum[u];
        for(auto i:g[u]) 
        {
            if(!in[i])
            {
                ind[i]--;
                if(check(i))
                {
                    q.push(i);
                    in[i]=i;
                }
            }
        }
            
    }
    cout<<ans<<'\n';
}

signed main()
{
    FAST;
    int __=1;
    //cin>>__;
    while(__--) {
        solve();
    }

    return 0;
}

C++(clang++11) 解法, 执行用时: 1008ms, 内存消耗: 304264K, 提交时间: 2021-05-09 20:40:22 

#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 10;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
char a[N][N];
int vis[N][N],cnt[N*N],type[N*N],in[N*N],n;
int all[N*N],d[N*N],sz;
vector<int> g[N*N];
unordered_map<int,int> m[N*N];
bool ok(int i){
	if(type[i]==0) return d[i] < all[i];
	else return d[i]<=1;
}
void dfs(int x,int y,int c){
	vis[x][y] = c, cnt[c]++;
	for(int i=0;i<4;i++){
		int tx = x + dx[i], ty = y + dy[i];
		if(1<=tx&&tx<=n&&1<=ty&&ty<=n&&!vis[tx][ty]&&a[tx][ty]==a[x][y]) dfs(tx,ty,c);
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>(a[i]+1);
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(!vis[i][j]){
		sz++; dfs(i,j,sz);
		type[sz] = (a[i][j]=='.'?0:1);
	}
	for(int x=1;x<=n;x++) for(int y=1;y<=n;y++){
		set<int> s;
		for(int i=0;i<4;i++){
			int tx = x + dx[i], ty = y + dy[i];
			if(1<=tx&&tx<=n&&1<=ty&&ty<=n){
				if(vis[tx][ty]!=vis[x][y]){
					s.insert(vis[tx][ty]);
				}
			}
		}
		for(int t: s) m[t][vis[x][y]]++;
	}
	for(int i=1;i<=sz;i++){
		if(type[i]==0){
			for(auto [k,v]: m[i]) g[k].push_back(i), d[i]++;
		}
		else{
			for(auto [k,v]: m[i]){
				if(v!=cnt[k]) continue;
				g[k].push_back(i), d[i]++;
			}
		}
	}
	for(int i=1;i<=sz;i++) all[i] = d[i];
	queue<int> q;
	for(int i=1;i<=sz;i++) if(ok(i)) q.push(i), in[i] = 1;
	int ans = 0;
	while(!q.empty()){
		int u = q.front(); q.pop();
		if(type[u]) ans += cnt[u];
		for(int v: g[u]) if(!in[v]){
			d[v]--;
			if(ok(v)){
				in[v] = 1; q.push(v);
			}
		}
	}
	cout<<ans<<endl;
}

上一题

© 2024 nowcoder.com