这两个题比较相似，放到一起来整理。

FZU 1275
放火烧山

法外狂徒张三在n*m的平地上放火玩，#表示草，张三有分身，他的分身和他本人分别选一个#格子点火，火可以向上向下向左向右在有草的格子蔓延，点火的地方时间为0，蔓延至下一格的时间依次加一。求烧完所有的草需要的最少时间。如不能烧完输出-1。

第一行，输入一个T,表示有T组测试数据。
每组数据由一个n，m分别表示行列
1 <= T <=100, 1 <= n <=10, 1 <= m <=10

思路：基本就是广度优先搜素，由于数据量不大，可以任意寻找合适的点来bfs。bfs的内容就是计算从这两个点出发烧完所有草的时间，然后更新。

代码：

#include <iosream>
#include <string>
#include <queue>
using namespace std;
const int INF=1e5;
int step[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int board[11][11]; // map
int cost[11][11]; // 花费的时间
int visit[11][11]; // 这个点有没有访问到
int ans=INF;
int m,n;
void get_ans() // 更新最值的函数
{int res=-1;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(board[i][j] &&!visit[i][j])return;	if(board[i][j] && cost[i][j]>res) res=cost[i][j];}}if(res<ans) res=ans;
}
void bfs(int x1,int y1,int x2,int y2)
{for(int i=0;i<m;i++)for(int j=0;j<n;j++){cost[i][j]=-1,visit[i][j]=0;}queue< pair<int,int> >q; // 要注意这个用法q.push(pair<int,int>(x1,y1)); // push进去visit[x1][y1]=1;cost[x1][y1]=0; // 初始化if(!visit[x2][y2]){q.push(pair<int,int>(x2,y2));cost[x2][y2]=0;visit[x2][y2]=1;}while(!q.empty()){pair<int,int> t=q.front();q.pop();for(int i=0;i<4;i++){ // 关键循环int x=t.first; int y=t.second; // x位置，y位置x+=step[i][0];y+=step[i][1];if(x>=0&&x<m&&y>=0&&y<n&&!visit[x][y]&&board[x][y]){visit[x][y]=1;cost[x][y]=cost[t.first][t.second]+1;q.push(pair<int,int>(x,y)); // 合适的点就进队列} }}get_ans();// 每次bfs都要更新
}
int main()
{int t;cin>>t;for(int k=1;k<=t;k++){cin>>m>>n;for(int i=0;i<m;i++){string s;cin>>s;for(int j=0;j<n;j++){ // 这里不用原来的输入，转化成数字if(s[j]=='#') board[i][j]=1;else board[i][j]=0;}}for(int i=0;i<m;i++)for(int j=0;j<n;j++)for(int p=0;p<m;p++)for(int q=0;q<n;q++)bfs(i,j,p,q); // 数据量比较小，暴力if(ans!=inf) printf("Case %d: %d\n",k,ans);else printf("Case %d: -1\n",t);ans=INF;}
}

UVA 11624
乔在迷宫中工作。不幸的是，迷宫的一部分着火了，迷宫的主人没有制定火灾的逃跑计划。请帮助乔逃离迷宫。根据乔在迷宫中的位置以及迷宫的哪个方块着火，你必须确定火焰烧到他之前，乔是否可以离开迷宫，如果能离开他能跑多快。
乔和火每分钟移动一个方格，上、下、左、右，四个方向中的一个。火势向四个方向同时蔓延。乔可以从迷宫的任何一个边界逃离迷宫。无论是乔还是火都不会到达有墙的位置。

Input
第一行输入包含一个整数，即测试次数
每个测试用例的第一行包含两个
整数R和C，用空格分隔，1≤R，C≤1000
下面R行中，每一行都包含C个字符，以及每个字符是以下之一：# 代表墙
. 代表空地，火和乔是可通行的
J 乔在迷宫中最初的位置，火和乔是可通行的
F 代表火
在每组测试中只有一个J

思路：双bfs，乔和火两个bfs同步进行。

// UVa 11624 Fire
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int INF = 1e5;
int step[4][2]={{-1,0},{1,0},{0,-1},{0,1} };
int maze[1005][1005];
int cost_by_F[1005][1005];
int cost_by_J[1005][1005];
int visit[1005][1005];
int ans=INF;
int r,c;
void get_ans()
{for(int i=0;i<r;i++)for(int j=0;j<c;j++){if(i==0||j==0||i==r-1||j==c-1 && maze[i][j]){if(cost_by_F[i][j] > cost_by_J[i][j]){if(cost_by_J[i][j]<ans)ans=cost_by_J[i][j];}}}
}
void bfs(int x,int y,int cost[][1005],int choice)
{// 1是J// 2是Ffor(int i=0;i<r;i++)for(int j=0;j<c;j++){cost[i][j] =INF;visit[i][j]=0;}queue<pair<int,int> > q;// Jif(choice==1){q.push(pair<int,int>(x,y));visit[x][y]=1;cost[x][y]=1;}// Felse{for(int i=0;i<r;i++)for(int j=0;j<c;j++){if(maze[i][j]==2){q.push(pair<int,int>(i,j));visit[i][j]=1;cost[i][j]=1;}}}while(!q.empty()){pair<int,int> t = q.front();q.pop();for(int i=0;i<4;i++){int x=t.first,y=t.second;x+=step[i][0],y+=step[i][1];if(x>=0&&x<r&&y>=0&&y>=0&&y<c&&!visit[x][y]&&maze[x][y]){visit[x][y]=1;cost[x][y]=cost[t.first][t.second]+1;q.push(pair<int,int> (x,y));}}}
}
int main()
{int n;cin>>n;for(int k=1;k<=n;k++){cin>>r>>c;int x,y;for(int i=0;i<r;i++){string s;cin>>s;for(int j=0;j<c;j++){if(s[j]=='#') maze[i][j]=0;else if(s[j]=='.') maze[i][j]=1;else if(s[j]=='F') maze[i][j]=2;else{maze[i][j]=1;x=i,y=j;}}}bfs(x,y,cost_by_J,1);bfs(x,y,cost_by_F,2);get_ans();if(ans!=INF)cout<<ans<<endl;elsecout<<"IMPOSSIBLE"<<endl;ans=INF;}
}

反思：

1. 建图可以不按照原来的符号，用自己定义的数字。