UVa 1600 Patrol Robot——bfs

UVa 1600 Patrol Robot——bfs

三维数组判重

#include #include #include #include #include using namespace std;const int dx[] = {-1, 1, 0, 0};const int dy[] = {0, 0, -1, 1};int G[50][50], m, n, k, vis[50][50][20];struct Node { int x, y, step, k;};bool edge(int x, int y) { if (0 <= x && x < m && 0 <= y && y < n) return true; else return false;}int bfs() { memset(vis, 0, sizeof(vis)); queue q; q.push((Node){0, 0, 0, 0}); vis[0][0][0] = 1; while (!q.empty()) { Node temp = q.front(); q.pop(); if (temp.x == m - 1 && temp.y == n - 1) return temp.step; for (int i = 0; i < 4; i++) { int tx = temp.x + dx[i], ty = temp.y + dy[i], ts = temp.step + 1, tk = temp.k; if (G[tx][ty]) tk++; else tk = 0; if (edge(tx, ty) && tk <= k && !vis[tx][ty][tk]) { vis[tx][ty][tk] = 1; q.push((Node){tx, ty, ts, tk}); } } } return -1;}int main(){ int T; scanf("%d", &T); while (T--) { scanf("%d %d %d", &m, &n, &k); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { scanf("%d", &G[i][j]); } } printf("%d\n", bfs()); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。