每日一道Leetcode - 剑指 Offer 13. 机器人的运动范围【DFS|BFS】

DFS:

Python版本

class Solution:def movingCount(self, m: int, n: int, k: int) -> int:def dfs(i,j,si,sj):# 1. 超出边界 2. 数位和超出k 3.当前坐标节点已经访问过了if i>=m or j>=n or si+sj > k or (i,j) in visited:return 0# 将满足条件的访问过的坐标节点存到visited集合中，避免重复计算visited.add((i,j))# 最后返回的是当前节点的+右边的满足条件的解+下边的满足条件的解return 1+dfs(i+1,j,si+1 if (i+1)%10 else si-8,sj)+dfs(i,j+1,si,sj+1 if (j+1)%10 else sj - 8)visited = set()return dfs(0,0,0,0)

Java版本：

class Solution {int m,n,k;boolean[][] visited;public int movingCount(int m, int n, int k) {this.m = m;this.n = n;this.k = k;this.visited = new boolean[m][n];return dfs(0,0,0,0);}public int dfs(int i, int j,int si, int sj){if(i>=m || j>=n || si+sj >k || visited[i][j]) return 0;visited[i][j] = true;return 1 + dfs(i+1,j,(i+1)%10!=0?si+1:si-8,sj)+dfs(i,j+1,si,(j+1)%10!=0?sj+1:sj-8);}}

BFS

使用队列

python版本

class Solution:def movingCount(self, m: int, n: int, k: int) -> int:queue = [(0,0,0,0)]visited = set()while queue:i,j,si,sj=queue.pop(0)if i>=m or j>=n or si+sj>k or (i,j) in visited:continuevisited.add((i,j))queue.append((i+1,j,si+1 if (i+1)%10 else si-8,sj))queue.append((i,j+1,si,sj+1 if (j+1)%10 else sj-8))return len(visited)

Java版本：

class Solution {public int movingCount(int m, int n, int k) {boolean[][] visited = new boolean[m][n];int res = 0;Queue<int[]> queue = new LinkedList<int[]>();queue.add(new int[] {0,0,0,0});while(queue.size()>0){int[] x = queue.poll();int i = x[0], j=x[1],si=x[2],sj=x[3];if(i>=m || j>=n || si+sj>k || visited[i][j]) continue;visited[i][j]=true;res++; queue.add(new int[] {i+1,j,(i+1)%10 !=0?si+1:si-8,sj});queue.add(new int[] {i,j+1,si,(j+1)%10!=0?sj+1:sj-8});}return res;}}