【POJ - 1970】The Game（dfs）

sky-stars 2019-07-17 原文

【POJ – 1970】The Game（dfs）

–>The Game

直接中文

Descriptions:

判断五子棋棋局是否有胜者，有的话输出胜者的棋子类型，并且输出五个棋子中最左上的棋子坐标；没有胜者输出0。棋盘是这样的，如图

Sample Input

1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 2 0 0 2 2 2 1 0 0 0 0 0 0 0 0 0 0
0 0 1 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output

1
3 2

题目链接：
https://vjudge.net/problem/POJ-1970

五子棋，但是有点小坑，不能六子连在一起，简单说就是只能5颗棋子在一起

从上到下、从左到右遍历棋盘，当位置(x, y)有棋子时，则从该位置开始dfs，加上搜索的方向为向右(x, y+1)，向下(x+1, y)，右下(x+1, y+1)，右上(x, y-1)，所以如果搜索的结果符合获胜的条件，则(x, y)就为最左上的位置。

除了坐标之外，还要加上方向vist[i][j][d]，表示在坐标(i, j)的d方向是否搜索过。

AC代码：

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 25
using namespace std;
int T;
int n=19;
int cnt;
int vis[Maxn][Maxn][Maxn];//vist[i][j][d] 坐标(i, j)的d方向是否搜索过
int mp[Maxn][Maxn];//棋盘
int dt[][2] = {{-1, 1}, {0, 1}, {1, 1}, {1, 0}};  //方向为右上、右、右下、下
void dfs(int x,int y,int k,int people)//（x,y） k方向 people哪个人的棋子
{
    vis[x][y][k]=1;
    int dx=x+dt[k][0];
    int dy=y+dt[k][1];
    if(dx>=1&&dy>=1&&dx<=n&&dy<=n&&mp[dx][dy]==people)
    {
        cnt++;
        dfs(dx,dy,k,people);
    }
}
int main()
{
    cin>>T;
    while(T--)
    {
        int f=0;//初始化
        MEM(vis,0);
        MEM(mp,0);
        for(int i=1; i<=n; i++)//存图
            for(int j=1; j<=n; j++)
                cin>>mp[i][j];
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(mp[i][j])//不为0，开始搜
                {
                    int people=mp[i][j];//看看是谁下的棋
                    for(int k=0;k<4;k++)//四个方向
                    {
                        if(!vis[i][j][k])
                        {
                            cnt=1;//棋子的个数
                            dfs(i,j,k,people);
                            //5颗棋子，防止左上角之前还有一个棋子
                            if(cnt==5&&mp[i-dt[k][0]][j-dt[k][1]]!=people)
                            {
                                f=1;
                                cout<<people<<endl;
                                cout<<i<<" "<<j<<endl;
                                break;
                            }
                        }
                    }
                }
            }
        }
        if(f==0)
            cout<<"0"<<endl;
    }
}