算法1
(暴力枚举) $O(n^m)$
和矩阵中路径相似,暴力枚举每个O能否变化为‘X’,但是一直过不了,有以下的原因
- 矩阵中的上下左右方向的表示法会和正交坐标串了;
- 状态没有恢复;
- 算法不够好,没有小到包含这些算法
- A不了,就是记录一下
时间复杂度
参考文献
java 代码
class Solution {
public void solve(char[][] board) {
if(board.length==0) return;
int vis[][] = new int[board.length][board[0].length];
for(int i = 0;i<board.length;i++){
for(int j = 0;j<board[0].length;j++){
if(board[i][j]=='O') dfs(i,j,board,vis);
}
}
}
public boolean dfs(int x,int y,char[][] board,int[][] vis){
if(vis[x][y]==2) return false;
if(board[x][y]=='X') return true;//碰到了要改变的
if(x==0||x==board.length-1||y==0||y==board[0].length-1) return false;//进来是‘O’,但是已经到达了边界
vis[x][y]=1;
int dx[] = new int[]{0,-1,0,1};
int dy[] = new int[]{-1,0,1,0};//错了两次了,矩阵的这个方向要搞清楚
boolean cur=true;
for(int i = 0;i<4;i++){
x +=dx[i];
y +=dy[i];
if(vis[x][y]==2) cur=false;
else if(x>=0&&x<board.length&&y>=0&&y<board[0].length&&vis[x][y]==0)
{
cur=cur&&dfs(x,y,board,vis);
}
x = x-dx[i];
y = y-dy[i];
if(x==7&&y==8) System.out.println(cur);
if(!cur) break;
}
if(!cur) vis[x][y]=2;//表示这一位已经是不能改变了
if(cur) {board[x][y]='X';vis[x][y]=0;}
return cur;
}
}
算法2
(官方) $O(n^m)$
dfs
时间复杂度
参考文献
java 代码
class Solution {
int n,m;
public void solve(char[][] board) {
//我们只遍历矩阵边上的点,将它能到达的'O'全部变成A,最后将A变成X
n = board.length;
if(n==0) return;
m = board[0].length;
//遍历边界
for(int i = 0;i<n;i++){
dfs(board,i,0);
dfs(board,i,m-1);
}
for(int i =0;i<m;i++){
dfs(board,0,i);
dfs(board,n-1,i);
}
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
if(board[i][j]=='A') board[i][j]='O';
else board[i][j]='X';
}
}
}
public void dfs(char[][] board,int x,int y){
if(x<0||x>=n||y<0||y>=m||board[x][y]!='O') return;
board[x][y]='A';
dfs(board,x,y-1);
dfs(board,x-1,y);
dfs(board,x,y+1);
dfs(board,x+1,y);
}
}
BFS 并查集 都能ac吧