A robot has to patrol around a rectangular area which is in a form of m x 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 iand 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 (1m, n20). The second line contains an integer number k (0k20). The ith line of the next m lines contains ninteger 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
3 2 5 0 0 1 0 0 0 0 0 0 1 0 4 6 1 0 1 1 0 0 00 0 1 0 1 10 1 1 1 1 00 1 1 1 0 02 2 0 0 1 1 0
Sample Output
7 10 -1
题目类型：BFS
算法分析：使用visited[i][j][v]数组表示走到(i, j)且已经通v个墙的状态是否已经访问过。对于走到的节点值为1且还能够向下一个状态走，则将该状态的能力值减1，步数加1；如果走到的节点值为0，则将能力值恢复为k(只有这样才能最大化能力值，求得最短步数)，步数加1。一直这样扩展节点，直到有一个状态的坐标为(X, Y)，最后输出该状态的步数
|
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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 |
#include <iostream> #include <fstream> #include <algorithm> #include <iomanip> #include <cstring> #include <cstdio> #include <cmath> #include <map> #include <string> #include <vector> #include <stack> #include <queue> #include <set> #include <list> #include <ctime> using namespace std; const int maxn = 36; const int INF = 66666666; const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; int row, col, k; int ans[maxn][maxn]; bool visited[maxn][maxn][maxn]; int minval; struct Node { int x, y, v, s; Node (int xx, int yy, int vv, int ss) : x (xx), y (yy), v (vv), s (ss) {} Node () {} }; inline bool Inside (int x, int y, int v) { if (x >= 1 && x <= row && y >= 1 && y <= col) { if (ans[x][y]) { if (!visited[x][y][v+1]) return true; else return false; } else { if (!visited[x][y][0]) return true; else return false; } } return false; } void bfs (int x, int y, int v, int s) { memset (visited, false, sizeof (visited)); minval = INF; visited[x][y][v] = true; queue <Node> q; q.push (Node (x, y, v, s)); while (!q.empty ()) { Node temp = q.front (); q.pop (); if (temp.x == row && temp.y == col) { minval = temp.s; return ; } int i; for (i = 0; i < 4; i++) { if (Inside (temp.x + dx[i], temp.y + dy[i], temp.v)) { int val_x = temp.x + dx[i], val_y = temp.y + dy[i]; if (ans[val_x][val_y] && temp.v < k) { visited[val_x][val_y][temp.v+1] = true; q.push (Node (val_x, val_y, temp.v + 1, temp.s + 1)); } else if (!ans[val_x][val_y]) { visited[val_x][val_y][0] = true; q.push (Node (val_x, val_y, 0, temp.s + 1)); } } } } } int main() { // freopen ("aaa.txt", "r", stdin); int t; scanf ("%d", &t); while (t--) { scanf ("%d%d%d", &row, &col, &k); int i, j; for (i = 1; i <= row; i++) { for (j = 1; j <= col; j++) scanf ("%d", &ans[i][j]); } bfs (1, 1, 0, 0); if (minval == INF) printf ("-1\n"); else printf ("%d\n", minval); } return 0; } |
- « 上一篇：uva1588
- uva10168：下一篇 »