Description
某个著名的原始突然发生大火。这个森林的树非常有特点，长非常的整齐。我们可以假设森林大小是N*M的矩阵，那每个整数点坐标上都会种着一棵树。
经过调查发现，火灾发生的时候是由于其中K棵树同时着火了。并且开始蔓延到其他周边的树。已经计算出，每棵着火的树一分钟后会把火扩展到他旁边和他距离为1的树。
由于这个森林的树种很珍贵，但火灾扩展速度太快，为了得到更多的救援时间，救援队希望能至少救下最后一棵树。现在想请你计算出最后一棵被烧着的树在哪个位置？
Input
第一行：两个整数N,M(1 < = N , M < = 2000)，表示森林的大小。树都种在(x, y)的整数点上 (1 ≤ x ≤ N, 1 ≤ y ≤ M)。
第二行：一个整数K(1 <= K <= 10)，表示最开始着火的树的数目。
第三行：K对整数。每对整数表示最初烧着的树的位置。
第二行：一个整数K(1 <= K <= 10)，表示最开始着火的树的数目。
第三行：K对整数。每对整数表示最初烧着的树的位置。
Output
两个整数，表示最后一棵烧着的树的位置。（如果存在多棵最后烧着的树，输出最左上的那棵，即X坐标最小，如X坐标相同，Y坐标最小）
Sample Input
3 3
1
2 2
1
2 2
Sample Output
1 1
Source
思路：这道题用暴力可以过，我贴出来是因为我第二遍AC用了BFS，这道题还可以看成是一道简单的BFS题
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<queue>
using namespace std;
int map[2002][2002];
int dir[4][2]={1,0,0,1,-1,0,0,-1};
int main()
{
queue<int>q;
int n,m,k,i,x,y,a,b,xt,yt;
memset(map,0,sizeof(map));
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=k;i++)
{
scanf("%d%d",&x,&y);
q.push(x);
q.push(y);
map[x][y]=1;
}
while(!q.empty())
{
a=q.front();
q.pop();
b=q.front();
q.pop();
for(i=0;i<4;i++)
{
xt=a+dir[i][0];
yt=b+dir[i][1];
if(!map[xt][yt]&&xt<=n&&xt>0&&yt<=m&&yt>0)
{
q.push(xt);
q.push(yt);
map[xt][yt]=1;
}
}
}
printf("%d %d\n",a,b);
return 0;
}