UVa1600 - Patrol Robot
题设
1600 Patrol Robot
A robot has to patrol around a rectangular area which is in a form of m × n grid (m rows and n columns). The rows are labeled from 1 to m. The columns are labeled from 1 to n. A cell (i, j) denotes the cell in row i and column j in the grid. At each step, the robot can only move from one cell to an adjacent cell, i.e. from (x,y) to (x + 1,y), (x,y + 1), (x − 1,y) or (x,y − 1). Some of the cells in the grid contain obstacles. In order to move to a cell containing obstacle, the robot has to switch to turbo mode. Therefore, the robot cannot move continuously to more than k cells containing obstacles.
Your task is to write a program to find the shortest path (with the minimum number of cells) from cell (1, 1) to cell (m, n). It is assumed that both these cells do not contain obstacles.
Input
The input consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.
For each data set, the first line contains two positive integer numbers m and n separated by space (1 ≤ m, n ≤ 20). The second line contains an integer number k (0 ≤ k ≤ 20). The i-th line of the next m lines contains n integer aij separated by space (i = 1,2,…,m; j = 1,2,…,n). The value of aij is ‘1’ if there is an obstacle on the cell (i,j), and is ‘0’ otherwise.
Output
For each data set, if there exists a way for the robot to reach the cell (m, n), write in one line the integer number s, which is the number of moves the robot has to make; ‘-1’ otherwise.
Sample Input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
3
2 5
0
0 1 0 0 0
0 0 0 1 0
4 6
1
0 1 1 0 0 0
0 0 1 0 1 1
0 1 1 1 1 0
0 1 1 1 0 0
2 2
0
0 1
1 0
Sample Output
1
2
3
7
10
-1
题解
本题看似是一道非常经典的BFS，但在第一次提交中发现TLE，说明需要更深的考量，这是最开始的代码：
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
62
63
64
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 30;
const int dr[] = {1, 0, -1, 0};
const int dc[] = {0, 1, 0, -1};
int board[maxn][maxn];
int dist[maxn][maxn][maxn];
int r0, c0, r1, c1;
int m, n, k;
struct Node {
int r, c, t, l;
Node(int r, int c, int t = 0, int l = 0) : r(r), c(c), t(t), l(l) {}
};
void solve() {
memset(board, 0, sizeof(board));
memset(dist, 50, sizeof(dist));
scanf("%d %d", &m, &n);
scanf("%d", &k);
r0 = c0 = 1;
r1 = m;
c1 = n;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &board[i][j]);
}
}
queue<Node> q;
q.push({r0, c0});
while (!q.empty()) {
Node u = q.front();
q.pop();
if (u.r == r1 && u.c == c1) {
printf("%d\n", u.l);
return;
}
for (int i = 0; i < 4; i++) {
int r = u.r + dr[i];
int c = u.c + dc[i];
int t = u.t;
if (r >= 1 && r <= m && c >= 1 && c <= n) {
if (board[u.r][u.c])
t += 1;
else
t = 0;
if (t > k) continue;
int l = u.l + 1;
q.push({r, c, t, l});
}
}
}
printf("-1\n");
}
int main() {
int kase;
scanf("%d", &kase);
while (kase--) {
solve();
}
}
后发现，对于一个点来说，若走到该点经过的障碍数最少，则该路径最为优先，其余路径直接舍弃即可，于是用一个数组vis来记录最少障碍数。
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
62
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 30;
const int dr[] = {1, 0, -1, 0};
const int dc[] = {0, 1, 0, -1};
int board[maxn][maxn];
int vis[maxn][maxn];
int m, n, k;
struct Node {
int r, c, t, l;
Node(int r, int c, int t = 0, int l = 0) : r(r), c(c), t(t), l(l) {}
};
void solve() {
memset(board, 0, sizeof(board));
memset(vis, 50, sizeof(vis));
scanf("%d %d", &m, &n);
scanf("%d", &k);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &board[i][j]);
}
}
queue<Node> q;
q.push(Node(1, 1, 0, 0));
while (!q.empty()) {
Node u = q.front();
q.pop();
if (u.r == m && u.c == n) {
printf("%d\n", u.l);
return;
}
for (int i = 0; i < 4; i++) {
int r = u.r + dr[i];
int c = u.c + dc[i];
int t = u.t;
if (r < 1 || r > m || c < 1 || c > n) continue;
if (board[u.r][u.c])
t += 1;
else
t = 0;
if (t > k) continue;
int l = u.l + 1;
if (t < vis[r][c]) {
q.push(Node(r, c, t, l));
vis[r][c] = t;
}
}
}
printf("-1\n");
}
int main() {
int kase;
scanf("%d", &kase);
while (kase--) {
solve();
}
}