題目描述
地上有一個m行和n列的方格，一個機器人從坐標0,0的格子開始移動，每一次只能向左，右，上，下四個方向移動一格，但是不能進入行坐標和列坐標的數位之和大于k的格子， 例如，當k為18時，機器人能夠進入方格（35,37），因為3+5+3+7 = 18，但是，它不能進入方格（35,38），因為3+5+3+8 = 19，請問該機器人能夠達到多少個格子？
思路
記憶化搜索，時間復雜度O(mn)，空間復雜度O(mn)，
代碼
public class Solution {
private int k;
private int count;
private int row;
private int col;
private boolean[][] map;
private int[][] step = new int[][] {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
private boolean judge(int x, int y) {
if(x < 0 || x >= row || y < 0 || y >= col || map[x][y]) {
return false;
}
int sum = 0;
while(x > 0) {
sum += x % 10;
x /= 10;
}
while(y > 0) {
sum += y % 10;
y /= 10;
}
return sum <= k;
}
public void move(int x, int y) {
if(judge(x, y)) {
count++;
map[x][y] = true;
for (int i = 0; i < 4; i++) {
int r = x + step[i][0];
int c = y + step[i][1];
if (judge(r, c)) {
move(r, c);
}
}
}
}
public int movingCount(int threshold, int rows, int cols)
{
if(threshold < 0 || rows < 1 || cols < 1) {
return 0;
}
k = threshold;
row = rows;
col = cols;
map = new boolean[rows][cols];
move(0, 0);
return count;
}
}
筆記
無
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/57196.html
標籤：其他
上一篇：MATLAB中如何檢測輸入影像中任意三角形的三邊長，面積和重心？要利用標尺（標尺是自己手機拍的）求大佬指教啊啊啊啊
下一篇：剪繩子