建设买卖网站要多少钱,中国建设银行信用卡旅游卡服务网站,怎么看网站是否安装百度商桥代码,广告制作平台插#xff1a; 前些天发现了一个巨牛的人工智能学习网站#xff0c;通俗易懂#xff0c;风趣幽默#xff0c;忍不住分享一下给大家。点击跳转到网站。 坚持不懈#xff0c;越努力越幸运#xff0c;大家一起学习鸭~~~ 题目#xff1a;
给你一个下标从 0 开始的 8 x 8 网… 插 前些天发现了一个巨牛的人工智能学习网站通俗易懂风趣幽默忍不住分享一下给大家。点击跳转到网站。 坚持不懈越努力越幸运大家一起学习鸭~~~ 题目
给你一个下标从 0 开始的 8 x 8 网格 board 其中 board[r][c] 表示游戏棋盘上的格子 (r, c) 。棋盘上空格用 . 表示白色格子用 W 表示黑色格子用 B 表示。
游戏中每次操作步骤为选择一个空格子将它变成你正在执行的颜色要么白色要么黑色。但是**合法 **操作必须满足涂色后这个格子是 好线段的一个端点 好线段可以是水平的竖直的或者是对角线。
好线段 指的是一个包含 **三个或者更多格子包含端点格子**的线段线段两个端点格子为 同一种颜色 且中间剩余格子的颜色都为 另一种颜色 线段上不能有任何空格子。你可以在下图找到好线段的例子
给你两个整数 rMove 和 cMove 以及一个字符 color 表示你正在执行操作的颜色白或者黑如果将格子 (rMove, cMove) 变成颜色 color 后是一个 合法 操作那么返回 true 如果不是合法操作返回 false 。
示例 1
输入board [[.,.,.,B,.,.,.,.],[.,.,.,W,.,.,.,.],[.,.,.,W,.,.,.,.],[.,.,.,W,.,.,.,.],[W,B,B,.,W,W,W,B],[.,.,.,B,.,.,.,.],[.,.,.,B,.,.,.,.],[.,.,.,W,.,.,.,.]], rMove 4, cMove 3, color B
输出true
解释.W 和 B 分别用颜色蓝色白色和黑色表示。格子 (rMove, cMove) 用 X 标记。
以选中格子为端点的两个好线段在上图中用红色矩形标注出来了。示例2
输入board [[.,.,.,.,.,.,.,.],[.,B,.,.,W,.,.,.],[.,.,W,.,.,.,.,.],[.,.,.,W,B,.,.,.],[.,.,.,.,.,.,.,.],[.,.,.,.,B,W,.,.],[.,.,.,.,.,.,W,.],[.,.,.,.,.,.,.,B]], rMove 4, cMove 4, color W
输出false
解释虽然选中格子涂色后棋盘上产生了好线段但选中格子是作为中间格子没有产生以选中格子为端点的好线段。提示
board.length board[r].length 8 0 rMove, cMove 8 board[rMove][cMove] ‘.’ color 要么是 ‘B’ 要么是 ‘W’ 。
思路遇到此类数组题可以考虑使用dfs.
往8个方向dfs就行了。 时间复杂度O(1) 空间复杂度O(1)
java代码
class Solution {public boolean checkMove(char[][] board, int rMove, int cMove, char color) {int[][] dirs new int[][] {{0, -1}, {0, 1}, {-1, 0}, {1, 0}, {-1, -1}, {1, 1}, {-1, 1}, {1, -1}};//以rMove, cMove为起点向8个方向查找for (int[] dir : dirs) {int x dir[0], y dir[1];int r rMove x, c cMove y, middleCnt 0;while (isValid(r, c)) {// 如果中间有相反颜色的cnt0,并且找到了另一个端点和color相同则符合好线段直接返回trueif (middleCnt 0 board[r][c] color) return true;// 如果找到了空格则不符合break掉本次while循环if (board[r][c] .) break;//如果中间还没有相反的颜色下一个元素就和color相同则不符合break掉本次while循环if (middleCnt 0 board[r][c] color) break;// 走到这里表示这个元素和color不相同可以作为中间元素middleCnt;r x;c y;}}return false;}/*** 校验r、c是否走出数组边界*/private boolean isValid(int r, int c) {return 0 r r 8 0 c c 8;}
}
