【DFS+剪枝】个人练习-Leetcode-面试题 16.04. Tic-Tac-Toe LCCI-Toy模板网

这篇具有很好参考价值的文章主要介绍了【DFS+剪枝】个人练习-Leetcode-面试题 16.04. Tic-Tac-Toe LCCI。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接：https://leetcode.cn/problems/tic-tac-toe-lcci/

题目大意：给出一个N*N的棋盘格board[][]，走圈叉棋，判断输赢情况，某一方赢了返回该方的字符，若平局（棋盘满且没有一方赢）返回Draw，若结局未定（棋盘未满且没有一方赢）返回Pending

思路：可以DFS做，并做一部分剪枝优化。

首先判断主副对角线，因为一共只有两条，取board[0][0]和board[0][N-1]两个元素，然后DFS对角线即可，如果有胜利者的直接返回。

    bool searchDiag(vector<string>& board, char c) {
        int N = board.size();
        for (int i = 0; i < N; i++) {
            if (board[i][i] != c)
                return false;
        }
        return true;
    }

    bool searchViceDiag(vector<string>& board, char c) {
        int N = board.size();
        for (int i = 0; i < N; i++) {
            if (board[i][N-1-i] != c)
                return false;
        }
        return true;
    }

随后考虑行和列，我们用Xrow[], Xcol[]两个vector<bool>来表示第i行全是X或者第j列全是X的可能性。为true时表示目前为止还是有这种可能的，可以继续搜；为fasle表示这种可能已经排除了，不必再搜索。对于Orow[], Ocol[]同理。

遍历board[][]的每一个元素，非常必要的操作是

若board[i][j]非空，让计数器cnt自增，这个是用于判断Draw和Pending的
board[i][j]为X时，断绝Orow[i]和Ocol[j]的可能性，这就是在剪枝；同理为O时，断绝Xrow[i]和Xcol[j]的可能性；而当为空格时，断绝所有四种可能性

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == 'X') {
                    cnt++;
                    Orow[i] = Ocol[j] = false;
                    if (searchRC(i, j, board, 'X', Xrow, Xcol))
                        return "X";
                }
                else if (board[i][j] == 'O') {
                    cnt++;
                    Xrow[i] = Xcol[j] = false;
                    if (searchRC(i, j, board, 'O', Orow, Ocol))
                        return "O";
                }
                else
                    Xrow[i] = Xcol[j] = Orow[i] = Ocol[j] = false;
            }
        }

board[i][j]非空且存在可能性时，DFS整行和整列。若在DFS中发现整行或者整列的可能性被断绝了，及时更新并break跳出循环。若某种可能性成了，即该字符获胜，返回true；两种可能性都断绝时，返回false。

    bool searchRC(int i, int j, vector<string>& board, char c, vector<bool>& row, vector<bool>& col) {
        int pos, N = board.size();

        if (row[i]) {
            for (pos = j; pos < N; pos++) {
                if (board[i][pos] != c) {
                    row[i] = false;
                    break;
                }     
            }
            if (row[i])
                return true;
        }

        if (col[j]) {
            for (pos = i; pos < N; pos++) {
                if (board[pos][j] != c) {
                    col[j] = false;
                    break;
                }
            }
            if (col[j])
                return true;
        }

        return false;
    }

若没有获胜者，那么用cnt来判断Draw和Pending的情况。

        if (cnt == N*N)
            return "Draw";
        else
            return "Pending";

完整代码文章来源地址https://www.toymoban.com/news/detail-431462.html

class Solution {
public:
    bool searchRC(int i, int j, vector<string>& board, char c, vector<bool>& row, vector<bool>& col) {
        int pos, N = board.size();

        if (row[i]) {
            for (pos = j; pos < N; pos++) {
                if (board[i][pos] != c) {
                    row[i] = false;
                    break;
                }     
            }
            if (row[i])
                return true;
        }

        if (col[j]) {
            for (pos = i; pos < N; pos++) {
                if (board[pos][j] != c) {
                    col[j] = false;
                    break;
                }
            }
            if (col[j])
                return true;
        }

        return false;
    }

    bool searchDiag(vector<string>& board, char c) {
        int N = board.size();
        for (int i = 0; i < N; i++) {
            if (board[i][i] != c)
                return false;
        }
        return true;
    }

    bool searchViceDiag(vector<string>& board, char c) {
        int N = board.size();
        for (int i = 0; i < N; i++) {
            if (board[i][N-1-i] != c)
                return false;
        }
        return true;
    }


    string tictactoe(vector<string>& board) {
        int N = board.size();

        if (board[0][0] == 'X') {
            if(searchDiag(board, 'X'))
                return "X";
        }
        else if (board[0][0] == 'O') {
            if (searchDiag(board, 'O'))
                return "O";
        }
        else;

        if (board[0][N-1] == 'X') {
            if(searchViceDiag(board, 'X'))
                return "X";
        }
        else if (board[0][N-1] == 'O') {
            if (searchViceDiag(board, 'O'))
                return "O";
        }
        else;


        int cnt = 0;
        vector<bool> Xrow(N, true);
        vector<bool> Xcol(N, true);
        vector<bool> Orow(N, true);
        vector<bool> Ocol(N, true);


        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == 'X') {
                    cnt++;
                    Orow[i] = Ocol[j] = false;
                    if (searchRC(i, j, board, 'X', Xrow, Xcol))
                        return "X";
                }
                else if (board[i][j] == 'O') {
                    cnt++;
                    Xrow[i] = Xcol[j] = false;
                    if (searchRC(i, j, board, 'O', Orow, Ocol))
                        return "O";
                }
                else
                    Xrow[i] = Xcol[j] = Orow[i] = Ocol[j] = false;
            }
        }

        if (cnt == N*N)
            return "Draw";
        else
            return "Pending";
    }
};