LCP 41. 黑白翻转棋

题目描述

在 n*m 大小的棋盘中，有黑白两种棋子，黑棋记作字母 "X", 白棋记作字母 "O"，空余位置记作 "."。当落下的棋子与其他相同颜色的棋子在行、列或对角线完全包围（中间不存在空白位置）另一种颜色的棋子，则可以翻转这些棋子的颜色。

「力扣挑战赛」黑白翻转棋项目中，将提供给选手一个未形成可翻转棋子的棋盘残局，其状态记作 chessboard。若下一步可放置一枚黑棋，请问选手最多能翻转多少枚白棋。

注意：

若翻转白棋成黑棋后，棋盘上仍存在可以翻转的白棋，将可以继续翻转白棋
输入数据保证初始棋盘状态无可以翻转的棋子且存在空余位置

示例 1：

输入：chessboard = ["....X.","....X.","XOOO..","......","......"]

输出：3

解释：可以选择下在 [2,4] 处，能够翻转白方三枚棋子。

示例 2：

输入：chessboard = [".X.",".O.","XO."]

输出：2

解释：可以选择下在 [2,2] 处，能够翻转白方两枚棋子。

示例 3：

输入：chessboard = [".......",".......",".......","X......",".O.....","..O....","....OOX"]

输出：4

解释：可以选择下在 [6,3] 处，能够翻转白方四枚棋子。

提示：

1 <= chessboard.length, chessboard[i].length <= 8
chessboard[i] 仅包含 "."、"O" 和 "X"

解法一：BFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


func max(nums ...int) int {
    res := nums[0]
    for _, val := range nums {
        if val > res {
            res = val
        }
    }
    return res
}

func flipChess(chessboard []string) int {
    dirs := [8][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}
    h, w := len(chessboard), len(chessboard[0])
    var judge func(board [][]byte, x, y, dx, dy int) bool
    judge = func(board [][]byte, x, y, dx, dy int) bool {
        x, y = x+dx, y+dy
        for x >= 0 && x < h && y >= 0 && y < w {
            if board[x][y] == 'X' {
                return true
            }
            if board[x][y] == '.' {
                return false
            }
            x, y = x+dx, y+dy
        }
        return false
    }
    var bfs func(board [][]byte, x, y int) int
    bfs = func(board [][]byte, x, y int) int {
        ret := 0
        var queue [][2]int
        queue = append(queue, [2]int{x, y})
        board[x][y] = 'X'
        for len(queue) > 0 {
            curX, curY := queue[0][0], queue[0][1]
            queue = queue[1:]
            for i := 0; i < len(dirs); i++ {
                dx, dy := dirs[i][0], dirs[i][1]
                if judge(board, curX, curY, dx, dy) {
                    nX, nY := curX+dx, curY+dy
                    for board[nX][nY] != 'X' {
                        queue = append(queue, [2]int{nX, nY})
                        board[nX][nY] = 'X'
                        nX, nY = nX+dx, nY+dy
                        ret++
                    }
                }
            }
        }
        return ret
    }

    ans := 0
    for i := 0; i < h; i++ {
        for j := 0; j < w; j++ {
            if chessboard[i][j] == '.' {
                board := make([][]byte, h)
                for k, str := range chessboard {
                    board[k] = []byte(str)
                }
                ans = max(ans, bfs(board, i, j))
            }
        }
    }
    return ans
}

官方题解如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57


class Solution {
public:
    const int dirs[8][2] = {
        {1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}
    };

    bool judge(const vector<string>& chessboard, int x, int y, int dx, int dy) {
        x += dx;
        y += dy;
        while (0 <= x && x < chessboard.size() && 0 <= y && y < chessboard[0].size()) {
            if (chessboard[x][y] == 'X') {
                return true;
            } else if (chessboard[x][y] == '.') {
                return false;
            }
            x += dx;
            y += dy;
        }
        return false;
    }

    int bfs(vector<string> chessboard, int px, int py) {
        int cnt = 0;
        queue<pair<int, int>> q;
        q.emplace(px, py);
        chessboard[px][py] = 'X';
        while (!q.empty()) {
            pair<int, int> t = q.front();
            q.pop();
            for (int i = 0; i < 8; ++i) {
                if (judge(chessboard, t.first, t.second, dirs[i][0], dirs[i][1])) {
                    int x = t.first + dirs[i][0], y = t.second + dirs[i][1];
                    while (chessboard[x][y] != 'X') {
                        q.emplace(x, y);
                        chessboard[x][y] = 'X';
                        x += dirs[i][0];
                        y += dirs[i][1];
                        ++cnt;
                    }
                }
            }
        }
        return cnt;
    }

    int flipChess(vector<string>& chessboard) {
        int res = 0;
        for (int i = 0; i < chessboard.size(); ++i) {
            for (int j = 0; j < chessboard[0].size(); ++j) {
                if (chessboard[i][j] == '.') {
                    res = max(res, bfs(chessboard, i, j));
                }
            }
        }
        return res;
    }
};