【剑指offer】机器人的运动范围

• 一开始读错题意，造数据很小5行4列，然后想当然的认为讨论可解，推出数学公式就ok，结果只过了小范围的数据（m,n<10的数据），凉了两个小时才幡然醒悟---读错题了。

// m行n列
public static int movingCount(int threshold, int rows, int cols) {
        int m = rows;
        int n = cols;
        int k = threshold;

        if (k > m * n) {
            return m * n;
        }

        if (k >= m) {
            return m * (k - m + 1) + (k + 1 <= n ? (m + 1) * m / 2 : (m + k - n + 2) * (m - k + n - 1) / 2);
        } else {
            return k + 1 <= n ? (k + 1) * (k + 2) / 2 : (2 * k - n + 3) * n / 2;
        }
    }

• 接着试想着遍历能不能行:结果也被推翻了... （这个还是蛮好想的，当m=10,n=10附近的方格会出现）

for (int i = 0; i <= m; i++) {
      for (int j = 0; j <= n; j++) {
         // 如果能从此方格的上面或左边走到，则可以到达此方格
      }
}

• 最后只好乖乖地写dfs和bfs，万分无奈，哎~

// dfs解法
public class Solution {

    private final int dx[] = {1, -1, 0, 0};
    private final int dy[] = {0, 0, 1, -1};

    public int sum(int x) {
        int ans = 0;
        while (x > 0) {
            ans += x % 10;
            x /= 10;
        }
        return ans;
    }

    public int move(int threshold, int rows, int cols, int x, int y, boolean[][] vis) {

        vis[x][y] = true;
        int ans = 0;
        for (int i = 0; i < 4; i++) { // 向四个方向走
            int X = x + dx[i];
            int Y = y + dy[i];

            if (X >= 0 && Y >= 0 && X < rows && Y < cols && !vis[X][Y] && sum(X) + sum(Y) <= threshold) {
                ans += move(threshold, rows, cols, X, Y, vis) + 1;
            }
        }
        return ans;
    }

    public int movingCount(int threshold, int rows, int cols) {
        if (threshold < 0 || rows <= 0 || cols <= 0) {
            return 0;
        }
        boolean[][] vis = new boolean[rows][cols];
        return move(threshold, rows, cols, 0, 0, vis) + 1;
    }
}
// bfs解法也很好写，大家可以试一下。