UVa 1600 Patrol Robot (习题 6-5)

时间：2024-08-27 12:34:56

传送门: https://uva.onlinejudge.org/external/16/1600.pdf

多状态广搜

网上题解: 给vis数组再加一维状态，表示当前还剩下的能够穿越的墙的次数，每次碰到墙，当前的k减去1,碰到0，当前的k变成最初的k。

vis[x][y][z]  x, y代表坐标  z表示k  当为真时说明该点剩余穿墙次数为k的状态已出现过

 #include <bits/stdc++.h>

 using namespace std;

 typedef struct Node{

     int x, y, step, k;

 } node;

 const int MAXN = ;

 const int INF = 0x3f3f3f3f;

 const int cx[] = {-, , , };

 const int cy[] = {, , -, };

 int n, m, k, ans;

 int maze[MAXN][MAXN];

 int vis[MAXN][MAXN][MAXN];

 void bfs(){

     queue<node> q;

     while(!q.empty()) q.pop();

     node cur ;

     cur.x = cur.y = ;

     cur.step = ;

     cur.k = k;

     q.push(cur);

     vis[cur.x][cur.y][cur.k] = ;

     while(!q.empty()){

         cur = q.front();

         q.pop();

         int x = cur.x, y = cur.y;

         if(x == n && y == m){

             ans = cur.step;

             return ;

         }

         node now;

         if(cur.k >= ){

             for(int i = ; i < ; ++i){

                 now.x = x + cx[i], now.y = y + cy[i];

                 now.step = cur.step + ;

                 now.k = maze[now.x][now.y] ? cur.k -  : k;

                 if(now.x <  || n < now.x || now.y <  || m < now.y || vis[now.x][now.y][now.k]) continue;

                 if(now.k >= ){

                     vis[now.x][now.y][now.k] = ;

                     q.push(now);

                 }

             }

         }

     }

 }

 int main(){

     int t;

     cin >> t;

     while(t--){

         cin >> n >> m >> k;

         memset(vis, , sizeof(vis));

         memset(maze, , sizeof(maze));

         for(int i = ; i <= n; ++i)

             for(int j = ; j <= m; ++j)

                 cin >> maze[i][j];

         ans = -;

         bfs();

         cout << ans << endl;

     }

     return ;

 }

相关文章