当前位置：网站首页>uva11624 Fire! (双bfs)

uva11624 Fire! (双bfs)

2022-08-09 08:11:00 【51CTO】

Joe works in a maze. Unfortunately, portions of the maze have
caught on ﬁre, and the owner of the maze neglected to create a ﬁre
escape plan. Help Joe escape the maze.
Given Joe’s location in the maze and which squares of the maze
are on ﬁre, you must determine whether Joe can exit the maze before
the ﬁre reaches him, and how fast he can do it.
Joe and the ﬁre each move one square per minute, vertically or
horizontally (not diagonally). The ﬁre spreads all four directions
from each square that is on ﬁre. Joe may exit the maze from any
square that borders the edge of the maze. Neither Joe nor the ﬁre
may enter a square that is occupied by a wall.
Input
The ﬁrst line of input contains a single integer, the number of test
cases to follow. The ﬁrst line of each test case contains the two
integers R and C, separated by spaces, with 1 ≤ R, C ≤ 1000. The
following R lines of the test case each contain one row of the maze. Each of these lines contains exactly
C characters, and each of these characters is one of:
• #, a wall
• ., a passable square
• J, Joe’s initial position in the maze, which is a passable square
• F, a square that is on ﬁre
There will be exactly one J in each test case.
Output
For each test case, output a single line containing ‘IMPOSSIBLE’ if Joe cannot exit the maze before the
ﬁre reaches him, or an integer giving the earliest time Joe can safely exit the maze, in minutes.
Sample Input
2
4 4
####
#JF#
#..#
#..#
3 3
###
#J.
#.F
Sample Output
3
IMPOSSIBLE

题目链接

思路：由于题中没有说有几个起火点所以要用一个队列来维护。

当在T秒时人移动过后对火点进行扩散

       
       #include <stdio.h>
       
       #include <queue>
       
       #include <string.h>
       
       using 
       
       namespace 
       
       std;
       
       char 
       
       map[
       
       1005][
       
       1005];
       
       bool 
       
       vis[
       
       1005][
       
       1005];
       
       bool 
       
       vis1[
       
       1005][
       
       1005];
       
       int 
       
       dir[
       
       4][
       
       2]
       
       ={
       
       1,
       
       0,
       
       -
       
       1,
       
       0,
       
       0,
       
       1,
       
       0,
       
       -
       
       1};
       
       int 
       
       n,
       
       m,
       
       st_x,
       
       st_y;
       
       struct 
       
       node
       
{
       
       int 
       
       x,
       
       y,
       
       t;
       
       friend 
       
       bool 
       
       operator 
       
       <(
       
       node 
       
       a,
       
       node 
       
       b)
       
  {
       
       return 
       
       a.
       
       t
       
       >
       
       b.
       
       t;
       
  }
       
};
       
       struct 
       
       node1
       
{
       
       int 
       
       x,
       
       y,
       
       t;
       
};
       
       bool 
       
       limit(
       
       int 
       
       x,
       
       int 
       
       y)
       
{
       
       if(
       
       x
       
       <
       
       0
       
       ||
       
       x
       
       ==
       
       n
       
       ||
       
       y
       
       <
       
       0
       
       ||
       
       y
       
       ==
       
       m
       
       ||
       
       vis[
       
       x][
       
       y]
       
       ||
       
       map[
       
       x][
       
       y]
       
       ==
       
       '#'
       
       ||
       
       map[
       
       x][
       
       y]
       
       ==
       
       'F')
       
       return 
       
       false;
       
       return 
       
       true;
       
}
       
       queue
       
       <
       
       node1
       
       >
       
       fire;
       
       void 
       
       fire_spread()
       
{
       
       node1 
       
       temp1,
       
       temp2;
       
       int 
       
       T
       
       =
       
       fire.
       
       front().
       
       t;
       
       while(
       
       !
       
       fire.
       
       empty())
       
  {
       
       temp1
       
       =
       
       temp2
       
       =
       
       fire.
       
       front();
       
       // printf("**%d %d %d**\n",temp1.x,temp1.y,temp1.t);
       
       if(
       
       temp1.
       
       t
       
       >
       
       T)
       
       break;
       
       fire.
       
       pop();
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       4;
       
       i
       
       ++)
       
    {
       
       int 
       
       xx
       
       =
       
       temp1.
       
       x
       
       +
       
       dir[
       
       i][
       
       1];
       
       int 
       
       yy
       
       =
       
       temp1.
       
       y
       
       +
       
       dir[
       
       i][
       
       0];
       
       if(
       
       !
       
       vis1[
       
       xx][
       
       yy]
       
       &&
       
       map[
       
       xx][
       
       yy]
       
       !=
       
       '#'
       
       &&
       
       xx
       
       >=
       
       0
       
       &&
       
       xx
       
       <
       
       n
       
       &&
       
       yy
       
       >=
       
       0
       
       &&
       
       yy
       
       <
       
       m)
       
      {
       
       // printf("%d %d %d\n",xx,yy,temp1.t);
       
       vis1[
       
       xx][
       
       yy]
       
       =
       
       true;
       
       vis[
       
       xx][
       
       yy]
       
       =
       
       true;
       
       temp1.
       
       x
       
       =
       
       xx;
       
       temp1.
       
       y
       
       =
       
       yy;
       
       temp1.
       
       t
       
       ++;
       
       fire.
       
       push(
       
       temp1);
       
      }
       
       temp1
       
       =
       
       temp2;
       
    }
       
  }
       
}
       
       int 
       
       bfs()
       
{
       
       node 
       
       temp1,
       
       temp2;
       
       priority_queue
       
       <
       
       node
       
       >
       
       s;
       
       while(
       
       !
       
       s.
       
       empty()) 
       
       s.
       
       pop(); 
       
       temp1.
       
       x
       
       =
       
       st_x,
       
       temp1.
       
       y
       
       =
       
       st_y,
       
       temp1.
       
       t
       
       =
       
       0;
       
       s.
       
       push(
       
       temp1);
       
       while(
       
       !
       
       s.
       
       empty()) 
       
  {
       
       temp1
       
       =
       
       temp2
       
       =
       
       s.
       
       top();
       
       s.
       
       pop();
       
       //要让所有t时间的人走完 才对火进行扩散 
       
       if(
       
       temp1.
       
       t
       
       >
       
       fire.
       
       front().
       
       t)
       
       fire_spread();
       
       if(
       
       vis[
       
       temp1.
       
       x][
       
       temp1.
       
       y]) 
       
       continue;
       
       if(
       
       temp1.
       
       x
       
       ==
       
       0
       
       ||
       
       temp1.
       
       x
       
       ==
       
       n
       
       -
       
       1
       
       ||
       
       temp1.
       
       y
       
       ==
       
       0
       
       ||
       
       temp1.
       
       y
       
       ==
       
       m
       
       -
       
       1)
       
       return 
       
       temp1.
       
       t;
       
       vis[
       
       temp1.
       
       x][
       
       temp1.
       
       y]
       
       =
       
       true;
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       4;
       
       i
       
       ++)
       
    {
       
       int 
       
       xx
       
       =
       
       temp1.
       
       x
       
       +
       
       dir[
       
       i][
       
       0];
       
       int 
       
       yy
       
       =
       
       temp1.
       
       y
       
       +
       
       dir[
       
       i][
       
       1];
       
       if(
       
       limit(
       
       xx,
       
       yy))
       
      {
       
       temp1.
       
       x
       
       =
       
       xx;
       
       temp1.
       
       y
       
       =
       
       yy;
       
       temp1.
       
       t
       
       ++;
       
       s.
       
       push(
       
       temp1);
       
      }
       
       temp1
       
       =
       
       temp2;
       
    }
       
  }
       
       return 
       
       -
       
       1;
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       ncase;
       
       scanf(
       
       "%d",
       
       &
       
       ncase);
       
       while(
       
       ncase
       
       --)
       
  {
       
       memset(
       
       map,
       
       false,
       
       sizeof(
       
       map));
       
       memset(
       
       vis,
       
       false,
       
       sizeof(
       
       vis));
       
       memset(
       
       vis1,
       
       false,
       
       sizeof(
       
       vis1));
       
       while(
       
       !
       
       fire.
       
       empty()) 
       
       fire.
       
       pop();
       
       scanf(
       
       "%d %d",
       
       &
       
       n,
       
       &
       
       m);
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       n;
       
       i
       
       ++)
       
    {
       
       getchar();
       
       for(
       
       int 
       
       j
       
       =
       
       0;
       
       j
       
       <
       
       m;
       
       j
       
       ++)
       
      {
       
       scanf(
       
       "%c",
       
       &
       
       map[
       
       i][
       
       j]);
       
       if(
       
       map[
       
       i][
       
       j]
       
       ==
       
       'F')
       
        {
       
       node1 
       
       temp;
       
       vis[
       
       i][
       
       j]
       
       =
       
       vis1[
       
       i][
       
       j]
       
       =
       
       true;
       
       temp.
       
       x
       
       =
       
       i,
       
       temp.
       
       y
       
       =
       
       j,
       
       temp.
       
       t
       
       =
       
       0;
       
       fire.
       
       push(
       
       temp);
       
        }
       
       if(
       
       map[
       
       i][
       
       j]
       
       ==
       
       'J')
       
       st_x
       
       =
       
       i,
       
       st_y
       
       =
       
       j;
       
      }
       
    }
       
       int 
       
       result
       
       =
       
       bfs();
       
       if(
       
       result
       
       ==-
       
       1)
       
       printf(
       
       "IMPOSSIBLE\n");
       
       else
       
       printf(
       
       "%d\n",
       
       result
       
       +
       
       1);
       
  }
       
       return 
       
       0;
       
}
      
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.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15742657/5557836

当前位置：网站首页>uva11624 Fire! (双bfs)

uva11624 Fire! (双bfs)

边栏推荐

猜你喜欢

随机推荐