【剑指offer】机器人的运动范围
机器人的运动范围
http://www.nowcoder.com/questionTerminal/6e5207314b5241fb83f2329e89fdecc8
- 一开始读错题意,造数据很小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解法也很好写,大家可以试一下。