題意：
? ? ?給1個n*m的網(wǎng)格，上面有的點能走，有的點不能走（墻），然后有的點是火源，火源和人一樣，每次都是上下左右四個方向蔓延，速度一樣是1，火也不可以從墻上跨過去，給你人的起點，終點是只要走到邊界就行，就是走出矩陣，問你最小逃生時間。


思路：
? ? ? 一開始小卡了一下，過了一會馬上反應(yīng)過來了，這個題算是基本的廣搜題吧！我們想下他跟我們見過的最最基本的廣搜有什么區(qū)別?是不是就是多了幾個火源，而火源的作用是什么，是不是就是在蔓延的時候把一些能走的點變成不能走了，既然火源的速度和人一樣，那么我們可以把火源和人全都放入隊列<記住，要先把所有的火源放進去，最后在放人>，然后所有點（火源還有人）走過的點都不能再走了，就完事了唄！這個題目有很多方法，如果你想的話 還可以先處理火源，把每個點最早到達的火源的時間記錄下來，用所有的火源把地圖處理完了之后再跑廣搜（這個是白書給出的思路），不過感覺寫著比較麻煩，我的代碼<一開始說的方法>在下面，具體細節(jié)可以看代碼。
? ? ??


#include<queue>
#include<stdio.h>
#include<string.h>

#define N 1000 + 10

using namespace std;

typedef struct
{
? ?int x ,y ,t ,mk;
}NODE;

NODE xin ,tou;
queue<NODE>q;
bool map[N][N];
int R ,C ,dir[4][2] = {0 ,1 ,0 ,-1 ,1 ,0 ,-1 ,0};

bool ok(int x ,int y)
{
? ?return x >= 1 && x <= R && y >= 1 && y <= C && !map[x][y];
}

int BFS()
{
? ?while(!q.empty())
? ?{
? ? ? tou = q.front();
? ? ? q.pop();
? ? ? for(int i = 0 ;i < 4 ;i ++)
? ? ? {
? ? ? ? ?xin.x = tou.x + dir[i][0];
? ? ? ? ?xin.y = tou.y + dir[i][1];
? ? ? ? ?xin.t = tou.t + 1;
? ? ? ? ?xin.mk = tou.mk;?
? ? ? ? ?if(xin.mk && (xin.x == 0 || xin.x == R+1 || xin.y == 0 || xin.y == C + 1))
? ? ? ? ?return xin.t;
? ? ? ? ?if(ok(xin.x ,xin.y))
? ? ? ? ?{
? ? ? ? ? ?
? ? ? ? ? ? map[xin.x][xin.y] = 1;
? ? ? ? ? ? q.push(xin);
? ? ? ? ?}
? ? ? }
? ?}
? ?return -1;
}

int main ()
{
? ?int i ,j ,Ans ,t ,mkx ,mky;
? ?char str[N];
? ?scanf("%d" ,&t);
? ?while(t--)
? ?{
? ? ? scanf("%d %d" ,&R ,&C);
? ? ? while(!q.empty())q.pop();
? ? ? for(i = 1 ;i <= R ;i ++)
? ? ? {
? ? ? ? ?scanf("%s" ,str);
? ? ? ? ?for(j = 0 ;j < C ;j ++)
? ? ? ? ?{
? ? ? ? ? ? if(str[j] == '.') map[i][j+1] = 0;
? ? ? ? ? ? else if(str[j] == '#') map[i][j+1] = 1;
? ? ? ? ? ? else if(str[j] == 'J')
? ? ? ? ? ? {
? ? ? ? ? ? ? ?map[i][j+1] = 1;
? ? ? ? ? ? ? ?mkx = i ,mky = j + 1;
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? map[i][j+1] = 1 ,xin.x = i ;
? ? ? ? ? ? ? ? xin.y = j + 1 ,xin.t = 0;
? ? ? ? ? ? ? ? xin.mk = 0;?
? ? ? ? ? ? ? ? q.push(xin);
? ? ? ? ? ? }
? ? ? ? ?}
? ? ? }
? ? ? xin.x = mkx ,xin.y = mky ,xin.t = 0 ,xin.mk = 1;
? ? ? q.push(xin);
? ? ? /* ? ??
? ? ? puts("***************");
? ? ? while(!q.empty())
? ? ? {
? ? ? ? ?tou = q.front();
? ? ? ? ?q.pop();
? ? ? ? ?printf("%d %d %d %d**\n" ,tou.x ,tou.y ,tou.t ,tou.mk);
? ? ? }
? ? ? puts("**************"); */
? ? ? Ans = BFS(); ?
? ? ? Ans == -1 ? puts("IMPOSSIBLE"):printf("%d\n" ,Ans);
? ?}
? ?return 0;
}
? ? ??
? ? ? ? ? ? ? ?
? ? ? ? ? ? ??
? ? ??
? ?




? ? ? ? ? ??
? ? ??
? ?


? ? ?

總結(jié)

以上是生活随笔為你收集整理的UVA11624大火蔓延的迷宫的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。