美文网首页算法
LCP 41. 黑白翻转棋

LCP 41. 黑白翻转棋

作者: 红树_ | 来源:发表于2023-06-20 17:51 被阅读0次

LC每日一题,参考LCP 41. 黑白翻转棋

题目

n*m 大小的棋盘中,有黑白两种棋子,黑棋记作字母 "X", 白棋记作字母 "O",空余位置记作 "."。当落下的棋子与其他相同颜色的棋子在行、列或对角线完全包围(中间不存在空白位置)另一种颜色的棋子,则可以翻转这些棋子的颜色。若下一步可放置一枚黑棋,请问选手最多能翻转多少枚白棋。
注意:

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

输入:chessboard = [".X.",".O.","XO."]
输出:2

输入:chessboard = [".......",".......",".......","X......",".O.....","..O....","....OOX"]
输出:4

提示:

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

解题思路

  • 深度优先搜索:对棋盘中每个可以填黑棋的位置.进行深度优先搜索,同时翻转白棋变为黑棋后需要对该黑棋深度优先搜索,也可以使用广度优先搜索用队列维护新的搜索点。

深度优先搜索

class Solution {
    int n,m;
    String[] chessboard;
    public int flipChess(String[] chessboard) {
        this.chessboard = chessboard;
        n = chessboard.length;
        m = chessboard[0].length();
        int ans = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(chessboard[i].charAt(j) == '.') { //可以放置黑棋
                    ans = Math.max(ans,get(i,j,newC()));
                }
            }
        }
        return ans;
    }
    //创建新的棋盘拷贝
    char[][] newC() {
        char[][] c = new char[n][m];
        for(int i = 0; i < n; i++) c[i] = chessboard[i].toCharArray();
        return c;
    }
    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
    //在i,j位置放置黑棋翻转的白棋数
    int get(int i, int j,char[][] cb) {
        int count = 0;
        //判断周围有没有白棋
        for(int[] dir : dirs) {
            int ni = i + dir[0], nj = j + dir[1];
            if(ni >= 0 && nj >= 0 && ni < n && nj < m && cb[ni][nj] == 'O') {
                //往dir方向继续找看有没有黑棋
                count += check(dir,ni,nj,cb);
            }
        }
        return count;
    }
    //返回能翻转该方向白棋的数量
    int check(int[] dir, int i, int j,char[][] cb) {
        //判断终点是否有黑棋
        int ni = i + dir[0],nj = j + dir[1];
        while(ni >= 0 && nj >= 0 && ni < n && nj < m && cb[ni][nj] == 'O') {
            ni += dir[0];
            nj += dir[1];
        }
        if(!(ni >= 0 && nj >= 0 && ni < n && nj < m) || cb[ni][nj] != 'X') return 0;
        //翻转白棋 统计数量
        int count = 0;
        ni = i;
        nj = j;
        while(ni >= 0 && nj >= 0 && ni < n && nj < m && cb[ni][nj] == 'O') {
            cb[ni][nj] = 'X';
            count += 1 + get(ni,nj,cb);//递归获取该黑棋的翻转数
            ni += dir[0];
            nj += dir[1];
        }
        return count;
    }
}

复杂度分析

  • 时间复杂度:O(n^2m^2max(n,m),枚举位置nm,dfs搜索nm x max(n.m)
  • 空间复杂度:O(n^2m^2),复制棋盘nm大小复制了nm次。

2023.06.21

相关文章

  • 老毛子华硕固件 lcp设置 设置错了导致网络卡

    不主动发送 lcp-echo(off) 是自动lcp响应间隔 否

  • 围棋

    黑白之间, 山河憔悴, 人生如棋, ...

  • 前端优化-LCP

    什么是LCP LCP是最大内容绘制的简称。LCP是用来测量感知加载速度。感知加载速度是以用户为中心的重要指标。因为...

  • 《棋》

    文/借醉 生活亦棋 黑白两子,黑夜或白天。 情绪亦棋 黑白两子,积极或消极。 思想亦棋 推一断二,举一而反三。 梦...

  • 一念之间

    人生如棋 棋如人生 黑白颠倒 颠倒黑白 小人君子 君子小人 一念之间 变幻万千 万物有相 皆有心生

  • 围棋

    黑白谁能用入玄 千回生死体方圆 黑白子组合如诗如画 变幻无穷 是竞技 是游戏 是艺术 更是文化 棋以气生 气尽棋亡...

  • lintcode 最长公共前缀

    给k个字符串,求出他们的最长公共前缀(LCP)样例在 "ABCD" "ABEF" 和 "ACEF" 中, LCP...

  • 棋说人生

    人生如棋,棋如人生!黑白阴阳,纷繁变化,交织着亘古的厮杀、挣扎、执着与热情! 笔者是个爱棋之人,围棋象棋五子棋等皆...

  • 戏仿《咏鹅》四首

    琴,琴,琴, 纤指传素心, 宮商角徵羽,伯牙觅知音! 棋,棋,棋,世局乱如迷, 黑白十九路,西屏悟天机! 书,书,...

  • 2016 Claire Check out list

    2016.3-2016.9 「今天2017LCP大选」 我也不知道自己哪里来的勇气,去竞选这个LCP,毕竟自己才待...

网友评论

    本文标题:LCP 41. 黑白翻转棋

    本文链接:https://www.haomeiwen.com/subject/yoayydtx.html