算法1
(dfs) $O(n^2)$
参考了大佬的思路,感觉这个思路又清晰又很严谨,流啤
时间复杂度
参考文献
java 代码
class Solution {
public int movingCount(int threshold, int rows, int cols)
{
boolean vis[][] =new boolean[rows][cols];
return dfs(threshold,0,0,vis);
}
public int dfs(int k,int i,int j,boolean vis[][]){
//基线条件
if(i<0||i>=vis.length||j<0||j>=vis[0].length||vis[i][j]||(i/10+i%10+j/10+j%10)>k)
return 0;
vis[i][j]=true;
return dfs(k,i+1,j,vis)+dfs(k,i,j+1,vis)+dfs(k,i-1,j,vis)+dfs(k,i,j-1,vis)+1;
}
}
算法2
(bfs) $O(n^2)$
y总的思路
时间复杂度
参考文献
java 代码
class Solution {
class Node{
int first;
int second;
public Node(int first,int second){
this.first=first;
this.second=second;
}
}
public boolean isLess(int x,int y,int shreshold){
int ans=0;
while(x!=0){ans+=x%10;x/=10;}
while(y!=0){ans+=y%10;y/=10;}
return ans<=shreshold?true:false;
}
public int movingCount(int threshold, int rows, int cols)
{
boolean vis[][] =new boolean[rows][cols];
int res=0;//存结果
if(rows==0||cols==0) return 0;
Queue<Node> q= new LinkedList<>();
q.offer(new Node(0,0));//(0,0)起点
vis[0][0]=true;
int[] dx=new int[]{-1,0,1,0};
int[] dy=new int[]{0,1,0,-1};
while(!q.isEmpty()){
Node t=q.poll();
res++;
for(int i=0;i<4;i++){
int x=t.first+dx[i];
int y=t.second+dy[i];
if(x>=0&&x<rows&&y>=0&&y<cols&&!vis[x][y]&&isLess(x,y,threshold)) {
q.offer(new Node(x,y));
vis[x][y]=true;
}
}
}
return res;
}
}