javascript 解法, 执行用时: 96 ms, 内存消耗: 46.6 MB, 提交时间: 2023-06-21 09:26:07

/**
 * @param {string[]} chessboard
 * @return {number}
 */
const dirs = [
    [1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]
];

function flipChess(chessboard) {
    let res = 0;
    for (let i = 0; i < chessboard.length; ++i) {
        for (let j = 0; j < chessboard[0].length; ++j) {
            if (chessboard[i][j] === '.') {
                res = Math.max(res, bfs(chessboard, i, j));
            }
        }
    }
    return res;
}

function bfs(chessboard, px, py) {
    const board = [];
    for (let i = 0; i < chessboard.length; ++i) {
        board[i] = chessboard[i].split('');
    }
    let cnt = 0;
    const queue = [];
    queue.push([px, py]);
    board[px][py] = 'X';
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [-1, 1], [1, -1], [1, 1]];
    while (queue.length > 0) {
        const t = queue.shift();
        for (let i = 0; i < 8; ++i) {
            if (judge(board, t[0], t[1], dirs[i][0], dirs[i][1])) {
                let x = t[0] + dirs[i][0], y = t[1] + dirs[i][1];
                while (board[x][y] !== 'X') {
                    queue.push([x, y]);
                    board[x][y] = 'X';
                    x += dirs[i][0];
                    y += dirs[i][1];
                    ++cnt;
                }
            }
        }
    }
    return cnt;
}

function judge(board, x, y, dx, dy) {
    x += dx;
    y += dy;
    while (0 <= x && x < board.length && 0 <= y && y < board[0].length) {
        if (board[x][y] === 'X') {
            return true;
        } else if (board[x][y] === '.') {
            return false;
        }
        x += dx;
        y += dy;
    }
    return false;
}

golang 解法, 执行用时: 0 ms, 内存消耗: 3.1 MB, 提交时间: 2023-06-21 09:25:50

func flipChess(chessboard []string) (ans int) {
	m, n := len(chessboard), len(chessboard[0])
	bfs := func(i, j int) int {
		q := [][2]int{{i, j}}
		g := make([][]byte, m)
		for i := range g {
			g[i] = make([]byte, n)
			copy(g[i], []byte(chessboard[i]))
		}
		cnt := 0
		for len(q) > 0 {
			p := q[0]
			q = q[1:]
			i, j = p[0], p[1]
			for a := -1; a <= 1; a++ {
				for b := -1; b <= 1; b++ {
					if a == 0 && b == 0 {
						continue
					}
					x, y := i+a, j+b
					for x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 'O' {
						x, y = x+a, y+b
					}
					if x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 'X' {
						x -= a
						y -= b
						cnt += max(abs(x-i), abs(y-j))
						for x != i || y != j {
							g[x][y] = 'X'
							q = append(q, [2]int{x, y})
							x -= a
							y -= b
						}
					}
				}
			}
		}
		return cnt
	}
	for i, row := range chessboard {
		for j, c := range row {
			if c == '.' {
				ans = max(ans, bfs(i, j))
			}
		}
	}
	return
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

java 解法, 执行用时: 4 ms, 内存消耗: 41.9 MB, 提交时间: 2023-06-21 09:24:59

class Solution {
    private int m;
    private int n;
    private String[] chessboard;

    public int flipChess(String[] chessboard) {
        m = chessboard.length;
        n = chessboard[0].length();
        this.chessboard = chessboard;
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (chessboard[i].charAt(j) == '.') {
                    ans = Math.max(ans, bfs(i, j));
                }
            }
        }
        return ans;
    }

    private int bfs(int i, int j) {
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {i, j});
        char[][] g = new char[m][0];
        for (int k = 0; k < m; ++k) {
            g[k] = chessboard[k].toCharArray();
        }
        int cnt = 0;
        while (!q.isEmpty()) {
            var p = q.poll();
            i = p[0];
            j = p[1];
            for (int a = -1; a <= 1; ++a) {
                for (int b = -1; b <= 1; ++b) {
                    if (a == 0 && b == 0) {
                        continue;
                    }
                    int x = i + a, y = j + b;
                    while (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 'O') {
                        x += a;
                        y += b;
                    }
                    if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 'X') {
                        x -= a;
                        y -= b;
                        cnt += Math.max(Math.abs(x - i), Math.abs(y - j));
                        while (x != i || y != j) {
                            g[x][y] = 'X';
                            q.offer(new int[] {x, y});
                            x -= a;
                            y -= b;
                        }
                    }
                }
            }
        }
        return cnt;
    }
}

python3 解法, 执行用时: 64 ms, 内存消耗: 16 MB, 提交时间: 2023-06-21 09:24:37

'''
bfs
枚举所有的空余位置作为下一步放置黑棋的位置，
然后使用广度优先搜索的方法计算在该位置下可以翻转的白棋的数量，找出最大值即可。
bfs(i, j) 定义为放置黑棋在(i, j)位置后，可以翻转的白旗数。
在函数中，我们使用队列来进行广度优先搜索，初始时将 (i,j) 放入队列中，
然后不断取出队首位置，遍历棋盘的八个方向，如果该方向上是一段连续的白棋，
且在末尾是黑棋，则将该黑棋之前的所有白棋都可以翻转，将这些白棋的位置放入队列中，
继续进行广度优先搜索。最后，我们返回可以翻转的白棋的数量。
'''
class Solution:
    def flipChess(self, chessboard: List[str]) -> int:
        def bfs(i: int, j: int) -> int:
            q = deque([(i, j)])
            g = [list(row) for row in chessboard]
            cnt = 0
            while q:
                i, j = q.popleft()
                for a, b in dirs:
                    x, y = i + a, j + b
                    while 0 <= x < m and 0 <= y < n and g[x][y] == "O":
                        x, y = x + a, y + b
                    if 0 <= x < m and 0 <= y < n and g[x][y] == "X":
                        x, y = x - a, y - b
                        cnt += max(abs(x - i), abs(y - j))
                        while x != i or y != j:
                            g[x][y] = "X"
                            q.append((x, y))
                            x, y = x - a, y - b
            return cnt

        m, n = len(chessboard), len(chessboard[0])
        dirs = [(a, b) for a in range(-1, 2) for b in range(-1, 2) if a != 0 or b != 0]
        return max(bfs(i, j) for i in range(m) for j in range(n) if chessboard[i][j] == ".")