【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=;

int cnt;

int vis[Maxn][Maxn][Maxn];//vist[i][j][d] 坐标(i, j)的d方向是否搜索过

int mp[Maxn][Maxn];//棋盘

int dt[][] = {{-, }, {, }, {, }, {, }};  //方向为右上、右、右下、下

void dfs(int x,int y,int k,int people)//（x,y） k方向 people哪个人的棋子

{

    vis[x][y][k]=;

    int dx=x+dt[k][];

    int dy=y+dt[k][];

    if(dx>=&&dy>=&&dx<=n&&dy<=n&&mp[dx][dy]==people)

    {

        cnt++;

        dfs(dx,dy,k,people);

    }

}

int main()

{

    cin>>T;

    while(T--)

    {

        int f=;//初始化

        MEM(vis,);

        MEM(mp,);

        for(int i=; i<=n; i++)//存图

            for(int j=; j<=n; j++)

                cin>>mp[i][j];

        for(int i=;i<=n;i++)

        {

            for(int j=;j<=n;j++)

            {

                if(mp[i][j])//不为0，开始搜

                {

                    int people=mp[i][j];//看看是谁下的棋

                    for(int k=;k<;k++)//四个方向

                    {

                        if(!vis[i][j][k])

                        {

                            cnt=;//棋子的个数

                            dfs(i,j,k,people);

                            //5颗棋子，防止左上角之前还有一个棋子

                            if(cnt==&&mp[i-dt[k][]][j-dt[k][]]!=people)

                            {

                                f=;

                                cout<<people<<endl;

                                cout<<i<<" "<<j<<endl;

                                break;

                            }

                        }

                    }

                }

            }

        }

        if(f==)

            cout<<""<<endl;

    }

}

巴特西

【POJ - 1970】The Game（dfs）

-->The Game

最新文章

热门文章