题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
回溯法
class Solution
{
public:
int movingCount(
int threshold,
int rows,
int cols)
{
bool *flags =
new bool[rows *
cols];
for (
int i =
0; i < rows * cols; i++
)
flags[i] =
false;
int res = helper(threshold, rows, cols,
0,
0, flags);
delete[] flags;
return res;
}
int helper(
int threshold,
int rows,
int cols,
int i,
int j,
bool *
flags)
{
if (i >= rows || j >= cols || i <
0 || j <
0 || flags[i * cols + j] ==
true || getBitSums(i) + getBitSums(j) >
threshold)
return 0;
flags[i * cols + j] =
true;
return helper(threshold, rows, cols, i +
1, j, flags) + helper(threshold, rows, cols, i -
1, j, flags) + helper(threshold, rows, cols, i, j +
1, flags) + helper(threshold, rows, cols, i, j -
1, flags) +
1;
}
int getBitSums(
int a)
{
int res =
0;
while (a >
0)
{
res += a %
10;
a /=
10;
}
return res;
}
};
转载于:https://www.cnblogs.com/ruoh3kou/p/10265784.html
