首页 > 试题广场 >

围棋棋盘上有一片连续的白子，没有黑子。请写一个函数，计算返回

[问答题]

围棋棋盘上有一片连续的白子，没有黑子。请写一个函数，计算返回该片白子的气数。函数输入参数为任一个白子的位置。

注：围棋规则：格子棋盘，棋子下在十字交叉点上，纵横线19*19。一片棋子，与其中任一子相邻的空交叉点称为这片子的1口气，所有这样的交叉点数量是这片子的气数。比如中央的单独一个棋子，上下左右4口气，气数为4；棋盘左上角的单独棋子，右边加下边两口气，气数是2；中央的两个相连的白子，气数为6。等等。

xxxxxxxxxxxxxxxa

给出了气数的定义，又给出了连续的前提条件。函数输入任意一白子的位置，返回该片白子的气数。

图论问题，且该图为连通图，可以使用DFS或者BFS，为了回顾知识，这里会采用两种方式去处理。

void change_axis(int &x,int & y,int i){
    switch(i){
        case 0:
        if(x>0)
         x-=1;
        break;
       case 1:
        if(y<18)
         y+=1;
        break;
       case 2:
        if(x<18)
         x+=1;
        break;
            case 3:
        if(y>0)
         y-=1;
        break;
    }
}
//DFS版本
void dfs(vector<vector<int>> & board,int x,int y,int & count){
    board[x][y]=-1;
    for(int i=0,tmp_x=x,tmp_y=y;i<4,++i){
        change_axis(x,y,i);
       if(board[x][y] == 1)
           dfs(board,x,y,count);
       else if(board[x][y] == 0){
             board[x][y]=-1;
          count++;
        }
       x=tmp_x,y=tmp_y;        
    }     
}
//BFS版本
int bfs(vector<vector<int>> & board,queue<vector<int>>& que,int x,int y){
    que.push({x,y});
    for(;!que.empty();){
        vector<int> tmp=que.pop(),save=tmp;
        for(int i=0;i<4;++i){
    change_axis(tmp[0],tmp[1],i);
    if(tmp == save)
          continue;
    if(board[tmp[0]][tmp[1]]==1){
          que.push(tmp);
          board[tmp[0]][tmp[1]]=-1;
    }
    else if(board[tmp[0]][tmp[1]]==0){
          board[tmp[0]][tmp[1]]=-1;
          count++;
    }    
        }  
    }
    return count;         
}

发表于 2018-07-30 10:36:46 回复(0)

赠君破阵歌

#include<string.h>
#include<stdio.h>

int vis[20][20];
int map[20][20];
int de[10][10] = {(-1,0),(1,0),(0,-1),(0,1)};
int cnt = 0;

int fun(int r,int v){
    int i,j;
    cnt+=4;
    for(int i=0;i<=3;i++){
        int x = r + de[i][0];
        int y = v + de[i][1];
        if(x<0 || x>=19) cnt--;//边缘
        if(y<0 || y>=19) cnt--;
        if(vis[x][y]) cnt--;//访问过

        if(!vis[x][y] && map[x][y]==1){//边缘是白
            vis[r][v] = 1;
            cnt += fun(x,y);
        }
    }
    return cnt;
}

int main(){
    int i,j;
    char map[20][20];
    for(i=0;i<19;i++){
        scanf("%s",map[i]);
    }
    int r,v;
    while(scanf("%d %d",r,v)!=EOF){
        memset(vis,0,sizeof(vis));
        printf("%d\n",fun(r,v));
    }

    return 0;
}

发表于 2018-03-04 15:24:47 回复(0)

deeplxx

int solution(vector<int>& nums, int m, int n) {

return count(nums, m, n);
}
int count(vector<vector<int>>& nums, int i, int j) {
if (i >= 0 && j >= 0 && i < (int)nums.size() && j < (int)nums.size()) {

if (nums[i][j] == 0) {

nums[i][j] = 2; // 修改遍历过的值避免重复

return 1;

}

        else if (nums[i][j] == 2) return 0;
        else {
            nums[i][j] = 2; // 修改遍历过的值避免重复
            return count(i-1, j) + count(i+1, j) + count(i, j-1) + count(i, j+1); // DFS
        }
    }
    return 0;
}

编辑于 2018-01-17 21:00:00 回复(0)

提交观点

问题信息

算法工程师唯品会 2018

来自：唯品会2018校招数据...

上传者：小小

难度：

3条回答 25收藏 2644浏览

围棋棋盘上有一片连续的白子，没有黑子。请写一个函数，计算返回

问题信息

热门推荐

相关试题