poj1970 -- The Game

最新推荐文章于 2020-05-04 23:30:04 发布

BestFSQ

最新推荐文章于 2020-05-04 23:30:04 发布

阅读量842

点赞数

分类专栏： POJ DFS 文章标签： dfs poj 五子棋

本文链接：https://blog.csdn.net/BestFSQ/article/details/71006729

版权

POJ 同时被 2 个专栏收录

11 篇文章

订阅专栏

DFS

8 篇文章

订阅专栏

本文介绍了一种高效的五子棋胜负判定算法。通过遍历棋盘上的棋子，并使用深度优先搜索（DFS）判断棋子是否构成五子连珠，从而确定黑方或白方获胜。特别地，算法考虑了不同方向上的连通性，确保了正确性和效率。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目链接

这题的目的是判断五子棋黑方或者白方哪一方获胜，或者都没有获胜，当有且只有五个同色的棋子横向，纵向，或对角线（主对角线和副对角线）方向排列时，该色棋子获胜。对于一个棋子来讲，它可以和其周围八个方向的棋子形成连子，但我们没必要把这八个方向全判断了，因为上与下可以合为一个方向，同理左与右，右上和左下，左上和右下也可分别合为一个方向，即横，纵，主对角线，副对角线，具体是下，右，右下，左上，因为这可以保证输出的是最左边或者最上边的棋子。实施起来就是逐个遍历棋盘的棋子，使用数组visit[r][c][dir]来判断位置(r,c)上是否朝方向dir访问过，然后在这四个方向上dfs即可。有一点需要注意：当在右上方向时dfs得到的结果为5时，我们还要注意右上方向的反方向即左下方向上有没有同色的棋子。具体代码如下：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

int board[20][20];  //棋盘
int visit[20][20][4];   //visit[r][c][dir],0未访问,1访问过
int dirs[4][2]={{-1,1},{0,1},{1,1},{1,0}};
bool win;
int cnt;    //当前相连的棋子个数

void dfs(int r,int c,int type,int dir)
{
    int nextr=r+dirs[dir][0];
    int nextc=c+dirs[dir][1];
    if(nextr>=0&&nextr<19&&nextc>=0&&nextc<19)
        if(board[nextr][nextc]==type)
    {
        visit[nextr][nextc][dir]=1;
        cnt++;
        dfs(nextr,nextc,type,dir);
    }
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        win=false;
        memset(board,0,sizeof(board));
        memset(visit,0,sizeof(visit));
        for(int i=0;i<19;i++)
            for(int j=0;j<19;j++)
            scanf("%d",&board[i][j]);
        for(int i=0;i<19;i++)
        {
            for(int j=0;j<19;j++)
            {
                if(!board[i][j])
                    continue;
                for(int k=0;k<4;k++)
                {
                    win=false;
                    cnt=1;
                    if(!visit[i][j][k])
                    {
                        visit[i][j][k]=1;
                        dfs(i,j,board[i][j],k);
                        if(cnt==5&&board[i-dirs[k][0]][j-dirs[k][1]]!=board[i][j]) //注意条件
                        {
                            win=true;
                            printf("%d\n%d %d\n",board[i][j],i+1,j+1);
                            break;
                        }
                    }
                }
                if(win) break;
            }
            if(win) break;
        }
        if(!win)
            cout<<0<<endl;
    }
    return 0;
}