題目大意：
給你一張迷宮圖，圖上有四種標記，分別代表人、火焰、牆壁、可以走的路，可能會有多個火焰，但人只有一個，火每單位時間會往上下左右擴展一步，人則可以選擇往四個方向走一步，但有火的地方不能走，問你人是否能安全逃出迷宮?如果可以還要輸出最短時間。
題目解法：
這題我原本的想法是，先讓全部的起火點都延伸一步，再讓人走一步，一直到人不能再走，或是人跑出迷宮就停止，也就是兩個BFS同時進行。但執行結果不如預期，吃了TLE!!
後來聽從學長的建議，兩個BFS分開進行，才勉強在1s的時限下過了。學長說原因是記憶體的存取會做相近記憶體的預load與cache，
所以一直access一樣或是相鄰的記憶體會速度比較快。因為同時進行BFS的話，會在記憶體間跳來跳去，速度較慢，而一次跑完一個的話，這樣速度較快。又學了一課啊!!!
原本TLE的部分Code
void expand()
{
int num = fire.size();
pos n;
pos t;
while(num --)
{
n = fire.front();
fire.pop();
for(int d = 0; d < 4; d ++)
{
t.x = n.x + dir[d][0];
t.y = n.y + dir[d][1];
if(inMaze(t.x, t.y) && maze[t.x][t.y] == '.')
{
maze[t.x][t.y] = 'F';
fire.push(t);
}
}
}
}
void move()
{
int num = person.size();
pos n;
pos t;
if(num == 0)
{
dead = true;
return;
}
while(num --)
{
n = person.front();
person.pop();
for(int d = 0; d < 4; d ++)
{
t.x = n.x + dir[d][0];
t.y = n.y+ dir[d][1];
if(!inMaze(t.x, t.y))
{
escape = true;
return;
}
if(maze[t.x][t.y] == '.')
{
maze[t.x][t.y] = 'J';
person.push(t);
}
}
}
}
int main()
{
......
......
int times = 0;
escape = false, dead = false;
while(true)
{
times ++;
expand();
move();
if(escape == true || dead == true)
break;
}
if(escape == true)
printf("%d\n", times);
if(dead == true)
printf("IMPOSSIBLE\n");
return 0;
}
花0.4s run的Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1002;
struct pos
{
int x, y;
};
int n, m;
char maze[N][N];
int dir[4][2] = { {1, 0}, {-1, 0}, {0, -1}, {0, 1} };
queue<pos> person;
queue<pos> fire;
int burn[N][N];
int visit[N][N];
bool escape;
int times;
inline bool inMaze(int x, int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void BFS_fire()
{
while(!fire.empty()) fire.pop();
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
if(maze[i][j] == 'F')
{
fire.push((pos){i, j});
burn[i][j] = 0;
}
else
{
burn[i][j] = -1;
}
}
}
pos n, t;
while(!fire.empty())
{
n = fire.front();
fire.pop();
for(int d = 0; d < 4; d ++)
{
t.x = n.x + dir[d][0];
t.y = n.y + dir[d][1];
if(inMaze(t.x, t.y) && maze[t.x][t.y] != '#')
{
if(burn[t.x][t.y] == -1)
{
burn[t.x][t.y] = burn[n.x][n.y] + 1;
fire.push(t);
}
}
}
}
}
void BFS_person()
{
while(!person.empty()) person.pop();
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
if(maze[i][j] == 'J')
{
person.push((pos){i, j});
visit[i][j] = 0;
}
else
{
visit[i][j] = -1;
}
}
}
pos n, t;
while(!person.empty())
{
n = person.front();
person.pop();
for(int d = 0; d < 4; d ++)
{
t.x = n.x + dir[d][0];
t.y = n.y + dir[d][1];
if(!inMaze(t.x, t.y))
{
escape = true;
times = visit[n.x][n.y] + 1;
return;
}
if(maze[t.x][t.y] != '#' && (burn[t.x][t.y] == -1 || visit[n.x][n.y] + 1 < burn[t.x][t.y]))
{
if(visit[t.x][t.y] == -1)
{
visit[t.x][t.y] = visit[n.x][n.y] + 1;
person.push(t);
}
}
}
}
}
int main()
{
int testcases;
scanf("%d", &testcases);
while(testcases --)
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i ++)
scanf("%s", maze[i] + 1);
escape = false;
BFS_fire();
BFS_person();
if(escape == true)
printf("%d\n", times);
else
printf("IMPOSSIBLE\n");
}
return 0;
}
天邊。世界 