BFS 队列

Plague Inc. is a famous game, which player develop virus to ruin the world.

JSZKC wants to model this game. Let's consider the world has N imes MN×M cities. The world has NN rows and MMcolumns. The city in the XX row and the YY column has coordinate (X,Y)(X,Y).

There are KK cities which are sources of infection at the 0^{th}0th day. Each day the infection in any infected city will spread to the near four cities (if exist).

JSZKC wants to know which city is the last one to be infected. If there are more than one cities , answer the one with smallest XX firstly, smallest YY secondly.

Input Format

The input file contains several test cases, each of them as described below.

The first line of the input contains two integers NN and MM (1 le N,M le 2000)(1≤N,M≤2000), giving the number of rows and columns of the world.
The second line of the input contain the integer KK (1 le K le 10)(1≤K≤10).
Then KK lines follow. Each line contains two integers X_iXi and Y_iYi, indicating (X_i,Y_i)(Xi,Yi) is a source. It's guaranteed that the coordinates are all different.

There are no more than 2020 test cases.

Output Format

For each testcase, output one line with coordinate XX and YY separated by a space.

样例输入

样例输出

1 1
1 3

其实这道题我是很气的，我加了队列超时，剪枝也超时。后面看到通过率挺高的，就怀疑是暴力水题，结果果然是这样。但是我还是写在博客上，帮助理解自己BFS；

超时代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define Swap(a,b,t) t=a,a=b,b=t
#define Mem0(x) memset(x,0,sizeof(x))
#define Mem1(x) memset(x,-1,sizeof(x))
#define MemX(x) memset(x,0x3f,sizeof(x));
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f;
const double eps=1e-12;
int n,m,k;
const int MAXN=2005;
int maxx,sum;
struct s{
   int x,y,second;
}map[MAXN][MAXN];
bool vis[MAXN][MAXN];
queue<s> q;
int dir[4][2]={-1,0,0,1,1,0,0,-1};
bool Solve(s f)
{
   if (f.x<=0||f.y<=0||f.x>n||f.y>m||vis[f.x][f.y])
       return false;
   return true;
}
void BFS()
{
   while (!q.empty())
   {
       if (sum==0)
           break;
       s f,node;
       node=q.front();
       q.pop();
       for (int t=0;t<4;t++){
           f.x=node.x+dir[t][0];
           f.y=node.y+dir[t][1];
           f.second=node.second;
           if (Solve(f)){
               f.second=node.second+1;
               map[f.x][f.y].second=f.second;
               sum--;
               vis[f.x][f.y]=true;
               q.push(f);
               maxx=f.second;
           }
       }
   }
}
int main()
{
   while (scanf("%d%d",&n,&m)!=EOF){
       sum=n*m;
       while (!q.empty())
           q.pop();
       memset(vis,0,sizeof(vis));
       for (int i=1;i<=n;i++){
           for (int j=1;j<=m;j++){
               map[i][j].second=0;
           }
       }
       scanf("%d",&k);

       sum-=k;
       int x,y,flag=1;
       for (int i=1;i<=k;i++){
           scanf("%d%d",&x,&y);
           map[x][y].x=x;
           map[x][y].y=y;
           map[x][y].second=1;
           vis[x][y]=true;
           q.push(map[x][y]);
       }
       if (n*m<=k){
           printf("1 1 ");
           continue;
       }
       BFS();
   /*   for (int i=1;i<=n;i++){
           for (int j=1;j<=m;j++)
               printf("%d ",map[i][j].second);
           cout<<endl;
       }   */
       for (int i=1;i<=n&&flag;i++){
           for (int j=1;j<=m;j++){
               if (map[i][j].second==maxx){
                   flag=0;
                   printf("%d %d ",i,j);
                   break;
               }
           }
       }
   }
   return 0;
}

暴力AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define Swap(a,b,t) t=a,a=b,b=t
#define Mem0(x) memset(x,0,sizeof(x))
#define Mem1(x) memset(x,-1,sizeof(x))
#define MemX(x) memset(x,0x3f,sizeof(x));
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f;
const double eps=1e-12;
int MAX;
int map[2010][2010];
int main()
{
   int n,m,k,x,y,cnt;
   while (scanf("%d%d",&n,&m)!=EOF){
       MAX=-inf;
       scanf("%d",&k);
       int g=k;
       MemX(map);
       while (k--){
//           system("pause");
           cin>>x>>y;
           for (int i=1;i<=n;i++){
               for (int j=1;j<=m;j++){
                   if (i==x||j==y)
                       map[i][j]=Min(map[i][j],abs(x-i)+abs(y-j));
                   else
                       map[i][j]=Min(map[i][j],abs(x-i)+abs(y-j)-1);
               }
           }
       }
       for (int i=1;i<=n;i++){
           for (int j=1;j<=m;j++){
               if (map[i][j]>MAX)
                   MAX=map[i][j];
           }
       }
/*   */   for (int i=1,flag=1;flag&&i<=n;i++){
           for (int j=1;j<=m;j++){
               if (MAX==map[i][j]){
                   flag=0;
                   printf("%d %d ",i,j);
                   break;
               }
           }
       }
   }
   return 0;
}