hdu 4543 —— 三足鼎立

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=4543

分两种情况：一种是所有点都是空地，剩下就是第二种。

第一种情况：三个点一定是在边上，否则总可以把点往边上挪，使得曼哈顿距离增加。这可以导出公式：

if(N == 1) return (M-1) / 2;

else if(M == 1) return (N-1) / 2;

else return (2*N + 2*M - 4)/3;

第二种情况：以全部被占领的点为起点，BFS遍历地图，得到每个空地距离被占领点的最小距离dis，然后对这些点排序后做三重循环，加入些优化。开始时想到这样会T掉，结果发现数据挺水的。

代码：

  1 //zzy.2013AC
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<iostream>
  5 #include<algorithm>
  6 using namespace std;
  7 
  8 struct P{
  9     int x,y,dis;
 10 };
 11 
 12 int N,M,pnum;
 13 int map[80][80],a[80][80];
 14 P queue[100000];
 15 int front,rear;
 16 char s[200];
 17 P point[10000];
 18 
 19 void push(P p){
 20     queue[rear++] = p;
 21 }
 22 
 23 P pop(){
 24     ++front;
 25     return queue[front - 1];
 26 }
 27 
 28 P D(P p,int dir){
 29     P p2 = p;
 30     if(dir == 0) --p2.x;
 31     else if(dir == 1) ++ p2.x;
 32     else if(dir == 2) -- p2.y;
 33     else ++p2.y;
 34     return p2;
 35 }
 36 
 37 bool check(P p){
 38     if(p.x >=0 && p.x < N && p.y >=0 && p.y < M && a[p.x][p.y] == 0)
 39         return true;
 40     return false;
 41 }
 42 
 43 void BFS()
 44 {
 45     rear = front = 0;
 46     for(int i=0; i<N; ++i)
 47         for(int j=0; j<M; ++j){
 48             if(a[i][j] == 1){
 49                 P p;
 50                 p.x = i;
 51                 p.y = j;
 52                 push(p);
 53             }
 54         }
 55     while(rear > front){
 56         P p = pop();
 57         for(int dir =0; dir < 4; dir ++){
 58             P p2;
 59             p2 = D(p,dir);
 60             if(check(p2)){
 61                 a[p2.x][p2.y] = a[p.x][p.y] + 1;
 62                 push(p2);
 63             }
 64         }
 65     }
 66 }
 67 
 68 bool cmp(P p1, P p2){
 69     return p1.dis < p2.dis;
 70 }
 71 
 72 int DIS(P p1,P p2){
 73     return abs(p1.x - p2.x) + abs(p1.y - p2.y);
 74 }
 75 
 76 int solve()
 77 {
 78     BFS();
 79     pnum = 0;
 80     for(int i=0; i<N; ++i){
 81         for(int j=0; j<M; ++j){
 82             if(a[i][j] > 1){
 83                 P p;
 84                 p.x = i;
 85                 p.y = j;
 86                 p.dis = a[i][j] - 1;
 87                 point[pnum++] = p;
 88             }
 89         }
 90     }
 91     if(pnum == 0){
 92         if(N == 1) return (M-1) / 2;
 93         if(M == 1) return (N-1) / 2;
 94         return (2*N + 2*M - 4)/3;
 95     }
 96     sort(point,point+pnum,cmp);
 97     int q = 0,d = 1;
 98     while(q < pnum){
 99         bool flag = false;
100         for(int i=q; i<pnum; ++i){
101             for(int j=i+1;j<pnum; ++j){
102                 if(DIS(point[i],point[j]) < d) continue;
103                 for(int k=j+1; k<pnum; ++k){
104                     if(DIS(point[i],point[k]) >= d &&
105                             DIS(point[j],point[k]) >= d){
106                         flag = true;
107                         break;
108                     }
109                 }
110                 if(flag) break;
111             }
112             if(flag) break;
113         }
114         if(flag == false) break;
115         ++d;
116         while(q < pnum && point[q].dis < d){
117             ++q;
118         }
119     }
120     return d-1;
121 }
122 
123 int main()
124 {
125     int T,cas = 0;
126     scanf("%d",&T);
127     while(T--){
128         ++cas;
129         int ans  = 1;
130         scanf("%d %d",&N,&M);
131         gets(s);
132         for(int i=0; i<N; ++i){
133             gets(s);
134             for(int j=0; j<M; ++j){
135                 map[i][j] = (s[j] == '.' ? 0 : 1);
136                 a[i][j] = map[i][j];
137             }
138         }
139         ans = solve();
140         printf("Case %d: %d\n",cas,ans);
141     }
142     return 0;
143 }