[BFS/DFS]HOJ2581Go

u010160562 · · 1524 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

传送门:Go

Go

My Tags   (Edit)
  Source : Stanford Programming Contest 2007
  Time limit : 1 sec   Memory limit : 64 M

Submitted : 201, Accepted : 117

In the game of Go, two players alternate placing black and white stones on lattice points of an n * n grid, each attempting to surround as much territory(i.e., regions of unfilled lattice points) as possible. At the end of the game, the score for each player is the total area of the territory surrounded by his or her stones. Given the locations of black and white stones on a Go board at the end of a match, your task is to compute the score of each player in order to determine the winner.

Formally, two grid lattice points with coordinates (r, c) and (r', c') are adjacent if |r - r'| + |c - c'| = 1. A connected region of unfilled lattice points belongs to one player's territory if all adjacent filled lattice points contain stones belonging to that player(see Figure 1). Finally, a player's score consists of the number of unfilled lattice points in his or her territory.

Figure 1: Diagram of a 9 * 9 Go board. Unfilled lattice points belonging to black's territory are marked with B, and unfilled lattice points belonging to white's territory are marked with W. Neutral unfilled lattice points are unmarked. In the game above, white wins by 21 - 3 = 18.

Input

The input test file will contain multiple cases, each consisting of three lines. Each test case begins with a line containing three integers, n(1 ≤ n ≤ 19), b and w(b ≥ 0, w ≥ 0 and 1 ≤ b + w ≤ n2). Here, n denotes the size of the board, b is the number of black pieces placed, and w is the number of white pieces placed. The second line of each test case contains b pairs of integers r1 c1 . . . rb cb (where 1 ≤ ri, ci ≤ n) indicating the positions of the b black stones. The third line of each test case contains w pairs of integers r'1 c'1 ... r'w c'w(1 ≤ r'i, c'i ≤ n) indicating the positions of the w white stones. No two stones will be located at the same lattice point. Input is terminated by a single line containing only the number 0; do not process this line.

Output

For each test case, print either "White wins by ____", "Black wins by ____", or "Draw".

Sample Input

1 1 0
1 1
2 0 1
1 1
5 12 4
1 1 1 2 1 3 2 1 2 3 3 1 3 3 4 1 4 3 5 1 5 2 5 3
1 4 2 4 3 4 3 5
0

Sample Output

Draw
White wins by 3
Black wins by 1

解题报告:

此题可以用DFS/BFS做。题意下围棋时黑子和白子哪个占的多,且黑白子不会重复在一个点。此题化简一下,把黑子占的地方赋值为1,白子占的地方赋值为2.空白的地方首先为0.

做法是:找到一个为0的点,进行BFS/DFS,把访问过的点赋值为3.当碰见点为1的就说明这块是黑子的,为2就说明为白子的。最后比较大小即可。


DFS:

#include<iostream>
#include<stack>
#include<cstdio>
#include<cstring>
using namespace std;
int maps[25][25];
struct node{
    int x,y;
}st;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int flagb,flagw,numb,numw,num;
void dfs(node st,int n){
    stack<node> q;
    int i;
    node a,b;
    while(!q.empty()){
        q.pop();
    }
    flagb=0;flagw=0;num=1;
    q.push(st);
    maps[st.x][st.y]=3;
    while(!q.empty()){
        a=q.top();
        q.pop();
        for(i=0;i<4;i++){
            b.x=a.x+dx[i];
            b.y=a.y+dy[i];
            if(b.x>0&&b.x<=n&&b.y>0&&b.y<=n){
                if(maps[b.x][b.y]==0){
                    maps[b.x][b.y]=3;
                    q.push(b);
                    num++;
                }
                else if(maps[b.x][b.y]==1)
                    flagb=1;
                else if(maps[b.x][b.y]==2)
                    flagw=1;
            }
        }
    }
}
int main(){
    int n,b,w,i,j,x,y;
    while(scanf("%d%d%d",&n,&b,&w)==3){
        flagb=0;flagw=0;numb=0;numw=0;num=0;
        memset(maps,0,sizeof(maps));
        //黑子为1
        for(i=1;i<=b;i++){
            scanf("%d%d",&x,&y);
            maps[x][y]=1;
        }
        //白子为2
        for(i=1;i<=w;i++){
            scanf("%d%d",&x,&y);
            maps[x][y]=2;
        }
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                if(maps[i][j]==0){
                    st.x=i;
                    st.y=j;
                    dfs(st,n);
                    if(flagb==0&&flagw==1)
                        numw+=num;
                    if(flagb==1&&flagw==0)
                        numb+=num;
                }
            }
        }
        if(numw==numb)
            printf("Draw\n");
        else if(numw>numb)
            printf("White wins by %d\n",numw-numb);
        else
            printf("Black wins by %d\n",numb-numw);
    }
    return 0;
}


BFS:

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
int maps[25][25];
struct node{
    int x,y;
}st;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int flagb,flagw,numb,numw,num;
void bfs(node st,int n){
    queue<node> q;
    int i;
    node a,b;
    while(!q.empty()){
        q.pop();
    }
    flagb=0;flagw=0;num=1;
    q.push(st);
    maps[st.x][st.y]=3;
    while(!q.empty()){
        a=q.front();
        q.pop();
        for(i=0;i<4;i++){
            b.x=a.x+dx[i];
            b.y=a.y+dy[i];
            if(b.x>0&&b.x<=n&&b.y>0&&b.y<=n){
                if(maps[b.x][b.y]==0){
                    maps[b.x][b.y]=3;
                    q.push(b);
                    num++;
                }
                else if(maps[b.x][b.y]==1)
                    flagb=1;
                else if(maps[b.x][b.y]==2)
                    flagw=1;
            }
        }
    }
}
int main(){
    int n,b,w,i,j,x,y;
    while(scanf("%d%d%d",&n,&b,&w)==3){
        flagb=0;flagw=0;numb=0;numw=0;num=0;
        memset(maps,0,sizeof(maps));
        //黑子为1
        for(i=1;i<=b;i++){
            scanf("%d%d",&x,&y);
            maps[x][y]=1;
        }
        //白子为2
        for(i=1;i<=w;i++){
            scanf("%d%d",&x,&y);
            maps[x][y]=2;
        }
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                if(maps[i][j]==0){
                    st.x=i;
                    st.y=j;
                    bfs(st,n);
                    if(flagb==0&&flagw==1)
                        numw+=num;
                    if(flagb==1&&flagw==0)
                        numb+=num;
                }
            }
        }
        if(numw==numb)
            printf("Draw\n");
        else if(numw>numb)
            printf("White wins by %d\n",numw-numb);
        else
            printf("Black wins by %d\n",numb-numw);
    }
    return 0;
}



有疑问加站长微信联系

本文来自:CSDN博客

感谢作者:u010160562

查看原文:[BFS/DFS]HOJ2581Go

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:812540095

1524 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传