首页 > 代码库 > HDU 1072 (不一样的入队条件) Nightmare

HDU 1072 (不一样的入队条件) Nightmare

2024-07-17 20:41:21   223人阅读

之前的BFS都是需要一个标记数组，但这个题不一样，因为可能一个格子不止走一次。

那么我们就要寻找新的入队条件：left比上次经过的时候大才入队(left表示上次经过该点时剩余的时间)。

为什么呢？我们重复走过一个点只有一个可能，那就是为了去取那个，所以如果取完后再回头经过这个点的时候剩余时间变多了，我们的目的就达到了。

left数组初值为0

优化：

重置时间的装置最多取一次就够了，所以可以再开一个标记数组vis记录装置是否用过。

 

 1 //#define LOCAL 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 using namespace std;  6  7 struct Point 8 { 9     int x, y;10     int steps;11     int time;12 }start, end;13 14 int map[10][10], vis[10][10], left[10][10];15 int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};16 int row, col;17 18 void BFS(void)19 {20     queue<Point> qu;21     start.time = 6, start.steps = 0;22     qu.push(start);23     while(!qu.empty())24     {25         Point fir = qu.front();26         qu.pop();27         if(fir.time == 0)    continue;28         if(fir.x == end.x && fir.y == end.y)29         {30             printf("%d\n", fir.steps);31             return;32         }33         if(map[fir.x][fir.y] == 4)34             fir.time = 6;35         for(int i = 0; i < 4; ++i)36         {37             int xx = fir.x + dir[i][0];38             int yy = fir.y + dir[i][1];39             if(xx<0 | xx>=row | yy<0 | yy>=col | (!map[xx][yy]))40                 continue;41             Point next;42             next.x = xx, next.y = yy;43             next.time = fir.time - 1;44             next.steps = fir.steps + 1;45             if(map[xx][yy] == 4 && vis[xx][yy])46                 continue;47             if(next.time > left[xx][yy])48             {49                 left[xx][yy] = next.time;50                 qu.push(next);51             }52         }53     }54     printf("-1\n");55 }56 57 int main(void)58 {59     #ifdef LOCAL60         freopen("1072in.txt", "r", stdin);61     #endif62 63     int T;64     scanf("%d", &T);65     while(T--)66     {67         scanf("%d%d", &row, &col);68         for(int i = 0; i < row; ++i)69             for(int j = 0; j < col; ++j)70             {71                 scanf("%d", &map[i][j]);72                 if(map[i][j] == 2)73                     start.x = i, start.y = j;74                 if(map[i][j] == 3)75                     end.x = i, end.y = j;76             }77         memset(vis, 0, sizeof(vis));78         memset(left, 0, sizeof(left));79         BFS();80     }81     return 0;82 }
代码君

 


联系
我们