-
Notifications
You must be signed in to change notification settings - Fork 0
/
M529_Minesweeper.java
79 lines (57 loc) · 2.02 KB
/
M529_Minesweeper.java
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
class Coordinate{
public int x;
public int y;
public Coordinate(int x, int y){
this.x = x;
this.y = y;
}
}
class Solution {
int dirs[][] = {{1,0}, {-1,0}, {0,1}, {0,-1}, {-1,-1}, {1,1}, {-1,1}, {1,-1}};
public char[][] updateBoard(char[][] board, int[] click) {
int i = click[0]; int j= click[1];
if(board[i][j]=='M'){
board[i][j] = 'X';
return board;
}
int[][] visited = new int[board.length][board[0].length];
//bfs algorithm
bfs(i, j, board, visited);
return board;
}
public void bfs (int i, int j, char[][] board, int[][] visited){
Queue<Coordinate> q = new LinkedList<>();
q.add(new Coordinate(i,j));
while(!q.isEmpty()){
Coordinate curr = q.poll();
i = curr.x; j= curr.y;
if(board[i][j]=='M')
board[i][j] = 'X';
else{
countAdjecentMine(i,j, board);
if(!Character.isDigit(board[i][j])){
board[i][j] = 'B';
for(int[] dir: dirs){
int r = i + dir[0]; int c =j+dir[1];
if(r>=0 && c>=0 && r<board.length && c<board[0].length && board[r][c]=='E'){
q.add(new Coordinate(r,c));
board[r][c] = 'B';
}
}
}
}
}
}
public void countAdjecentMine(int m, int n, char[][] board){
int count=0;
for(int[] dir: dirs){
int i= m + dir[0]; int j= n + dir[1];
if(i>=0 && j>=0 && i<board.length && j<board[0].length && (board[i][j]=='M' || board[i][j]=='X'))
count++;
}
if(count==0)
board[m][n] = 'B';
else
board[m][n] = (char) (count + '0');
}
}