《剑指offer》第13题 机器人的运动范围

Try two methods. One is BFS with the queue. The other is DFS with recursion.

import java.util.*;
public class Solution {
    // bfs with queue
    public final int[][] direction = {{-1,0},{0,1},{1,0},{0,-1}};
    public int movingCount(int threshold, int rows, int cols) {
        Queue<Cell> queue = new LinkedList<>();
        int[][] mark = new int[rows][cols];
        int count = 0;
        queue.offer(new Cell(0,0));
        while(!queue.isEmpty()) {
            Cell cell = queue.poll();
            int x = cell.x;
            int y = cell.y;
            if(x >= 0 && y >= 0 && x < rows && y < cols 
               && mark[x][y] == 0) {
                mark[x][y] = 1;
                if(cell.CheckCell(threshold)) {
                   count++;
                   for(int i = 0 ; i < direction.length;i++) {
                       int newX = x + direction[i][0];
                       int newY = y + direction[i][1];
                       queue.offer(new Cell(newX,newY));
                    }  
                }
            }
        }
        return count;
    }
    private class Cell {
        int x,y;
        public Cell(int x,int y) {
            this.x = x;
            this.y = y;
        }
        private boolean CheckCell(int threhold) {
            if(getSum(this.x) + getSum(this.y) > threhold) {
                return false;
            }
            return true;
        }
        private int getSum(int n) {
            int sum = 0;
            while(n != 0) {
                sum += n % 10;
                n = n / 10;
            }
            return sum;    
        }
    }
}


import java.util.*;
public class Solution {
    // dfs with recursion
    int count;
    public final int[][] direction = {{-1,0},{0,1},{1,0},{0,-1}};
    public Solution() {
       this.count = 0; 
    }
    public int movingCount(int threshold, int rows, int cols) {
        int[][] mark = new int[rows][cols];
        dfs(rows,cols,threshold,new Cell(0,0),mark);
        return count;
    }
    private void dfs(int rows,int cols,int threshold,Cell cell,int[][] mark) {
        int x = cell.x, y = cell.y;
        if(x < 0 || y < 0 || x >= rows || y >= cols || mark[x][y] == 1) {
            return;
        }
        mark[x][y] = 1;
        if(!cell.CheckCell(threshold)) {
            return;
        }
        count++;
        for(int i = 0; i < direction.length;i++) {
            int newX = x + direction[i][0];
            int newY = y + direction[i][1];
            dfs(rows,cols,threshold,new Cell(newX,newY),mark);
        }
    }
    private class Cell {
        int x,y;
        public Cell(int x,int y) {
            this.x = x;
            this.y = y;
        }
        private boolean CheckCell(int threhold) {
            if(getSum(this.x) + getSum(this.y) > threhold) {
                return false;
            }
            return true;
        }
        private int getSum(int n) {
            int sum = 0;
            while(n != 0) {
                sum += n % 10;
                n = n / 10;
            }
            return sum;    
        }
    }
}