题解 P1332 【血色先锋队】

本蒟蒻表示bfs太烦了，而且俗话说得好，暴力碾标算，N²过百万，打个暴力，何乐而不为呢~

中心思想是进行一个贪心：输入一个领主的位置，求出与所有感染源的曼哈顿距离，再取最小值，找到最近的一个感染源，输出感染源与这个领主的曼哈顿距离。

PS：曼哈顿距离

在平面上，坐标（x1, y1）的i点与坐标（x2, y2）的j点的曼哈顿距离为：
D( i , j )=| X1-X2 |+| Y1-Y2 |.

代码：

#include <bits/stdc++.h>
using namespace std;
int a,b,n,m;
int x[100005],y[100005];//储存感染源的位置
int jl(int p,int q)//计算曼哈顿距离的函数
{
  int ans=2147483647;
  for(int i=0; i<a; i++)
  {
    int t=abs(p-x[i])+abs(q-y[i]);//曼哈顿距离
    if(t<ans) ans=t;//cout<<ans<<endl;
  }
  return ans;
}
int main()
{
  cin>>n>>m>>a>>b;
  for(int i=0; i<a; i++)
    scanf("%d%d",&x[i],&y[i]);
  int t1,t2;
  for(int i=0; i<b; i++)
  {
    scanf("%d%d",&t1,&t2);
    cout<<jl(t1,t2)<<endl;//计算最小曼哈顿距离输出
  }
  return 0;
}

这就是窝的暴力之旅，各位886……