本文共 2417 字，大约阅读时间需要 8 分钟。

题目

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例

示例 1：

示例 2：

解法

1.深度优先遍历(一般用循环递归)

该题相当于遍历整个二维数组，来计算有多少个空格可以到达，我们可以考虑进行深度优先遍历的方法，首先要建立一个二维数组进行记录哪个遍历过，哪个没有遍历过。其中没一个数组结点块能够从四个方向到达，因为所有结点可以互相到达，我们又是从00点出发，所以考虑向下和向右两个方向能否到达就可以了。代码如下：

class Solution {    public int movingCount(int m, int n, int k) {        //建立一个标记的数组进行记录哪个可以访问        boolean[][] flag=new boolean[m][n];        //初始化计数值和起始点        int ans=1;        flag[0][0]=true;        for (int i = 0; i 
   
    k){                    continue;                }                //进行边界判断分别行往下走                if(i-1>=0){                    flag[i][j]|=flag[i-1][j];                }                进行边界判断分别行往右走                if(j-1>=0){                    flag[i][j]|=flag[i][j-1];                }                ans+=flag[i][j]?1:0;            }        }        return ans;    }    private static int get(int j) {        int ans=0;        while(j!=0){            ans+=j%10;            j=j/10;        }        return ans;    }}
   

2.广度优先遍历（一般用队列）

与1中描述相同，同样考虑向下和向右两个方向进行遍历，创建一个bool类型数组记录是否有被遍历过，数组dx[]={0，1}和dy[]={1,0}来进行控制是往右遍历还是往左遍历，(dx[0]，dy[0])是向右走一格，(dx[1]，dy[1])就是向左走一格。可以到达就加入队列，标记置为true。直到队列为空即可。

class Solution {    public int movingCount(int m, int n, int k) {        if (k == 0) {            return 1;        }        Queue
   
     queue = new LinkedList
    
     ();        // 向右和向下的方向数组        int[] dx = {0, 1};        int[] dy = {1, 0};        boolean[][] vis = new boolean[m][n];        queue.offer(new int[]{0, 0});        vis[0][0] = true;        int ans = 1;        while (!queue.isEmpty()) {            int[] cell = queue.poll();            int x = cell[0], y = cell[1];            for (int i = 0; i < 2; ++i) {                int tx = dx[i] + x;                int ty = dy[i] + y;                if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || get(tx) + get(ty) > k) {                    continue;                }                queue.offer(new int[]{tx, ty});                vis[tx][ty] = true;                ans++;            }        }        return ans;    }    private int get(int x) {        int res = 0;        while (x != 0) {            res += x % 10;            x /= 10;        }        return res;    }}
    
   

转载地址：http://ctgji.baihongyu.com/