基于深度优先搜索的围棋问题

下围棋
【问题描述】
小明是一个围棋高手，他在与任何人下棋时都能保持极高的胜率（大概百分之百吧）。当然高手也有烦恼，小明觉得每次落子以后查看自己是否赢（或者自己自杀了呵呵呵），都非常的麻烦，于是乎他找到了机智的你。
他现在处在一个棋局中，并且决定了他下一步的位置！现在他请你帮忙判断他的此次落子后棋局出现了什么变化。
【输入格式】
第1到9行是一个棋局，每一行有9个字符，分别用’.’、’O’、’X’来表示空白的位置、白色棋子、黑色棋子。
紧接一行为下一次落子位置x，y，chess，分别为x，y坐标与棋子颜色（颜色与棋盘表示方式相同）0<=x,y<=8。
【输出格式】
输出仅包含一行，如果小明落子后吃掉了对方，则输出”K.O.”；如果小明”自杀”了，则输出”Suicide”；如果没有吃子，则输出”Safe”。注意每次输出后需要换行。
【数据保证】
输入棋局均为合法字符，且为合法棋局。落子位置一定合法。
【输入样例】


注：此题用的深搜，搜的并非传统意义上的输赢，而是一步后的相关处理。
解析：
想要判断结果是K.O. 还是Suicide抑或Safe，就要知道他们的判断先后顺序—–这至关重要。我们不妨拿一种情况举例：
。。。。。。。。。
。。。。。。。。。
。。。 O。。。。。
。。O 。 O 。 。 。
。。X O X 。。。。
。。。X 。。。。。
。。。。。。。。。
。。。。。。。。。
。。。。。。。。。
3 3 X
此时应该为X棋子取胜，但是如果先判断是否自杀（Suicide），就应该是O棋KO了X棋—–这显然不是我们想要的。因此，我们判断的顺序应该是：先判断是否吃子（KO），再判断是否自杀（Suicide），最后，如果两种情况都不满足，那显然就是Safe了！

知道了这一点之后，我们再来分别分析三种情况：
1.是否KO对方：
我们可以把KO对方这一情况理解为：对于所有落点位置周围四个方向的棋子，只要有任何一个位置为对方棋子，那么则对该棋子进行有无气的检测**（DFS(x,y,op)来实现），加设全局变量flag并对其初始化为0，如果在DFS函数里得到 有气 这一状态，就让flag变为1，因为这样代表对方的一片棋子没有了气，这便可知己方KO了对手。
代码如下：**

void isEat(char ch, char op)
{
    //想要判断是否KO对手，只需要判断周围是否有对方子没有气
    //分别判断四个方向
    int cnt=0;
    flag = 0;
    if (boundary[m - 1][n] == op) {
        DFS(m - 1, n, op);if (flag==0) cnt ++;
    }
    flag = 0;
    if (boundary[m + 1][n] == op) {
        DFS(m + 1, n, op);if (flag==0) cnt ++;
    }
    flag = 0;
    if (boundary[m][n - 1] == op) {
        DFS(m, n - 1, op);if (flag==0) cnt ++;
    }
    flag = 0;
    if (boundary[m][n + 1] == op) {
        DFS(m, n + 1, op);if (flag==0) cnt ++;
    }
    flag = 0;
    if (cnt!=0) {
        printf("K.O.");system("pause");
        exit(0);
    }
}

2.是否自杀（Suicide）：
想要判断是否KO对方，需要给出的对方棋子的的符号（O或者X）来判断对方是否有气，而想要判断是否自杀，则只需要判断自己是否有气。
代码实现：

void isSuicide(char ch)
{
    memset(visit, 0, sizeof(visit));
    //判断是否自杀，只需要判断自身是否没有气
    flag = 0;
    DFS(m, n, ch);
    if (!flag) {
        printf("Suicide");
        system("pause");
        exit(0);
    }
}

3.是否安全（Safe）：
判断了前面的两种情况之后，第三种情况只需要一个else便可以实现，因为我在前面两个函数中，使他们如果满足条件就直接exit (0)，因此便有了下面的代码：

    //下面判断是否吃子
    isEat(ch,op);
    isSuicide(ch);
    //过滤掉两种情况后自然是Safe
    printf("Safe");
    system("pause");
    return 0;

———————————————————–以下是BFS函数的实现—————————————————————–

这里采用深度优先搜索的方法来搜索出指定点周围空格（也就是气）的是否存在，默认气不存在（flag=0），如果存在，则flag=1；
这里将已走过的点从0变为1用来记录，防止反复走重复的地方；

    visit[x][y] = 1;//走过变为1

递归不会无休止的进行，因此我们假定围棋棋盘有一圈额外的边界，一旦到达边界即停止搜索。满足以下条件即可return ,
1.到达边界

if (x == 0 || x == N - 1 || y == 0 || y == N - 1) return;

2.搜索到对方的子（此时便没有必要再进行搜索了）return；
3.搜索到空格（气），此时将flag标记为1，证明有气，return。

此时核心部分都已完成，完整代码如下（编译环境VS 2017）

#include<stdio.h>
#include<windows.h>
#include<stdlib.h>
#define N 11
char boundary[N][N];
int m, n,flag;
int visit[N][N];    //boundary用来存储棋局,visit用来存储移动操作（若已移动过的位置置1，否则为0代表可移动）
void DFS(int x, int y, char c);
void init_boundary(char str[N][N]);
void isEat(char ch, char op);
void isSuicide(char ch);
int main()
{
    char ch, str[N][N];
    char op; //相反子，若ch为O则op为X
    int i,j;
    init_boundary(str);
    fflush(stdin);
    scanf("%d %d %c", &m, &n, &ch);
    m++;
    n++;
    boundary[m][n] = ch;
    memset(visit, 0, sizeof(visit));//先将visit全部初始化为0,走过的地方变为1以记录
    ch == 'O' ? op = 'X' : op = 'O';
    for (i = 1;i <= N - 2;i++) {
        printf("\n");
        for (j = 1;j <= N - 2;j++)
            printf("%c ", boundary[i][j]);
    }
    //下面判断是否吃子
    isEat(ch,op);
    isSuicide(ch);
    //过滤掉两种情况后自然是Safe
    printf("Safe");
    system("pause");
    return 0;
}
void init_boundary(char str[N][N])
{
    int i, j;
    for (i = 1;i <= N - 2;i++)
    {
        for (j = 1;j <= N - 2;j++)
            boundary[i][j]=getchar();
        getchar();
    }
}
void isEat(char ch, char op)
{
    //想要判断是否KO对手，只需要判断周围是否有对方子没有气
    //分别判断四个方向
    int cnt=0;
    flag = 0;
    if (boundary[m - 1][n] == op) {
        DFS(m - 1, n, op);if (flag==0) cnt ++;
    }
    flag = 0;
    if (boundary[m + 1][n] == op) {
        DFS(m + 1, n, op);if (flag==0) cnt ++;
    }
    flag = 0;
    if (boundary[m][n - 1] == op) {
        DFS(m, n - 1, op);if (flag==0) cnt ++;
    }
    flag = 0;
    if (boundary[m][n + 1] == op) {
        DFS(m, n + 1, op);if (flag==0) cnt ++;
    }
    flag = 0;
    if (cnt!=0) {
        printf("K.O.");system("pause");
        exit(0);
    }
}
void isSuicide(char ch)
{
    memset(visit, 0, sizeof(visit));
    //判断是否自杀，只需要判断自身是否没有气
    flag = 0;
    DFS(m, n, ch);
    if (!flag) {
        printf("Suicide");
        system("pause");
        exit(0);
    }
}
void DFS(int x, int y, char c)
{
    visit[x][y] = 1;//走过变为1
    if (x == 0 || x == N - 1 || y == 0 || y == N - 1) return;
    if (boundary[x][y] == c) //如果本次和上次字符相同，则证明还可以深入
    {
        if (visit[x-1][y] == 0 ) DFS(x - 1, y, c);
        if (visit[x+1][y] == 0 ) DFS(x + 1, y, c);
        if (visit[x][y-1] == 0 ) DFS(x, y - 1, c);
        if (visit[x][y+1] == 0 ) DFS(x, y + 1, c);
        return;
    }
    else if (boundary[x][y] == '.') {
        flag = 1;
        return;
    }
    else
        return;
}