LCP 41. 黑白翻转棋
# LCP 41. 黑白翻转棋 (opens new window)
# 1.暴力枚举
分析：枚举棋盘所有空的位置落黑子。落子后搜索当前可翻转的所有白子的数目，在cal中有如下细节：
- 找到被包围的第一个白子。
- 对于被“包裹”的白子，虽然有八个方向，但是每两个方向构成一个"包裹“，比如上和下，因此只需要搜索四个方向。同时根据i和j枚举的方向，作为包裹起点的四个方向分别是左、左上、上、右上。
- 找到一个”包裹“样式后，将夹在中间的所有白子置为黑子。并计数。
- 递归统计棋盘中被包围的所有白子。如果当前这轮递归统计的可翻转白子数目为0，说明此时已无白子可翻转，递归结束。
class Solution {
int res=0;
public int flipChess(String[] chessboard) {
int[][] nums=new int[chessboard.length][chessboard[0].length()];
for(int i=0;i<nums.length;i++){
for(int j=0;j<nums[0].length;j++){
//黑棋
if(chessboard[i].charAt(j)=='X') nums[i][j]=1;
//白棋
if(chessboard[i].charAt(j)=='O') nums[i][j]=2;
}
}
int[][] copy=new int[chessboard.length][chessboard[0].length()];
for(int i=0;i<nums.length;i++){
for(int j=0;j<nums[0].length;j++){
if(nums[i][j]==0){
nums[i][j]=1;
copy(copy,nums);
cal(copy);
nums[i][j]=0;
}
}
public int cal(int[][] nums){
int temp=0;
for(int i=0;i<nums.length;i++){
for(int j=0;j<nums[0].length;j++){
if(nums[i][j]==2){
//水平方向
if(isvalid(nums,i,j-1)&&nums[i][j-1]==1&&nums[i][j]==2){
int x=i,y=j+1;
boolean has=false;
while(isvalid(nums,x,y)){
if(nums[x][y]==0) break;
if(nums[x][y]==1){
has=true;
break;
}
y++;
}
if(has){
x=i;
y=j;
while(isvalid(nums,x,y)){
if(nums[x][y]==1) break;
nums[x][y]=1;
temp++;
y++;
}
}
}
//左上方向
if(isvalid(nums,i-1,j-1)&&nums[i-1][j-1]==1&&nums[i][j]==2){
int x=i+1,y=j+1;
boolean has=false;
while(isvalid(nums,x,y)){
if(nums[x][y]==0) break;
if(nums[x][y]==1){
has=true;
break;
}
y++;
x++;
}
if(has){
x=i;
y=j;
while(isvalid(nums,x,y)){
if(nums[x][y]==1) break;
nums[x][y]=1;
temp++;
y++;
x++;
}
}
}
//竖直方向
if(isvalid(nums,i-1,j)&&nums[i-1][j]==1&&nums[i][j]==2){
int x=i+1,y=j;
boolean has=false;
while(isvalid(nums,x,y)){
if(nums[x][y]==0) break;
if(nums[x][y]==1){
has=true;
break;
}
x++;
}
if(has){
x=i;
y=j;
while(isvalid(nums,x,y)){
if(nums[x][y]==1) break;
nums[x][y]=1;
temp++;
x++;
}
}
}
//右上方向
if(isvalid(nums,i-1,j+1)&&nums[i-1][j+1]==1&&nums[i][j]==2){
int x=i+1,y=j-1;
boolean has=false;
while(isvalid(nums,x,y)){
if(nums[x][y]==0) break;
if(nums[x][y]==1){
has=true;
break;
}
y--;
x++;
}
if(has){
x=i;
y=j;
while(isvalid(nums,x,y)){
if(nums[x][y]==1) break;
nums[x][y]=1;
temp++;
y--;
x++;
}
}
}
}
}
}
if(temp==0) return 0;
int ans=temp+cal(nums);
res=Math.max(res,ans);
return ans;
}
public void copy(int[][]copy,int[][]nums){
for(int i=0;i<nums.length;i++){
for(int j=0;j<nums[0].length;j++){
copy[i][j]=nums[i][j];
}
}
}
public boolean isvalid(int[][] nums,int x,int y){
if(x<0||y<0||x>nums.length-1||y>nums[0].length-1) return false;
return true;
}
}
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
# 2.方向数组
使用方向数组控制每个方向上的搜索。
每次翻转白子变为黑子之后，将该位置加入队列中，判断该黑子的八个方向上是否存在新的可翻转的白子。
这种搜索策略相比前面对整个棋盘的递归而言，可以大大减少搜索次数。
int[][] dir=new int[][]{{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1}};
1
编辑 (opens new window)
上次更新: 2023/12/15, 15:49:57