题目描述
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。请问该机器人能够到达多少个格子？
题解
BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| bool sumup(int x, int y, int k)
{
int sum = x % 10 + (x % 100) / 10 + (x % 1000) / 100 + y % 10 + (y % 100) / 10 + (y % 1000) / 100;
if (sum <= k)return true;
return false;
}
int movingCount(int m, int n, int k) {
if (!k)return 1;
int count = 1;
bool** access =new bool*[m + 2];
for (int i = 0; i<m + 2; i++)
access[i] = new bool[n + 2];
for (int i = 0; i<m + 2; i++)
for (int j = 0; j<n + 2; j++)
access[i][j] = true;
for (int i = 0; i<m + 2; i++)
{
access[i][0] = false;
access[i][n + 1] = false;
}
for (int i = 0; i<n + 2; i++)
{
access[0][i] = false;
access[m + 1][i] = false;
}
access[1][1] = false;
queue<pair<int, int>> q;
q.push(make_pair(0,0));
while (!q.empty())
{
pair<int, int> p = q.front();
q.pop();
int x = p.first, y = p.second;
if (access[x + 2][y + 1] && sumup(x + 1, y, k))
{
q.push(make_pair(x + 1, y));
access[x + 2][y + 1] = false;
count++;
}
if (access[x][y + 1] && sumup(x - 1, y, k))
{
q.push(make_pair(x - 1, y));
access[x][y + 1] = false;
count++;
}
if (access[x + 1][y] && sumup(x, y - 1, k))
{
q.push(make_pair(x, y - 1));
access[x + 1][y] = false;
count++;
}
if (access[x + 1][y + 2] && sumup(x, y + 1, k))
{
q.push(make_pair(x, y + 1));
access[x + 1][y + 2] = false;
count++;
}
}
return count;
}
|
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：6.6 MB, 在所有 C++ 提交中击败了100.00%的用户
unbelievable。