Problem 3 基站建设 (station.cpp)———2019.10.6

在此郑重的感激wxyww大佬

wxyww tql

【题目描述】
小 Z 的爸爸是一位通信工程师，他所在的通信公司最近接到了一个新的通
信工程建设任务，他们需要在 C 城建设一批新的基站。
C 城的城市规划做得非常好，整个城市被规整地划分为 8 行 8 列共 64 个街
区，现在已知新基站需要建设在哪些街区，用字符“#”表示，而不需要建设基
站的街区用“.”表示。
爸爸告诉小 Z 说，建设基站最耗时的是基站两两之间互相通信的调试，每
建设一个新的基站，需要确保其与其他已经建好的基站之间能互相通信，若两
个基站的坐标分别为(x1,y1)和(x2,y2)，则调试所需时间大概为 max(|x1-
x2|,|y1-y2|)，而一个基站的总调试时间为与其他已经建好的基站的调试时间
中的最大值。现在爸爸想考考小 Z，看小 Z 能否计算出如何设计建设基站的顺
序，使得总的调试时间尽量少？

【输入格式】
输入一个 8 行 8 列的矩阵，全部由“#”和“.”组成。
【输出格式】
输出一个整数，表示花费的最少时间。
【样例输入一】
........
........
...#....
.#......
.......#
........
........
........
【样例输出一】
8
【样例输入二】
##..####
#####..#
..#.#...
#..##.##
.#.###.#
####.###
#.#...#.
##....#.
【样例输出二】
168
【数据范围】
设需要建设基站的街区数（即“#”的个数）为 n。

对于 30%的数据，n≤10；
对于 60%的数据，n≤20；
对于 100%的数据，n≤64。

记忆化搜索诶，，，

代码：

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<cstring>

 using namespace std;

 char mp[][];

 int f[][][][],tu[][];

 int dfs(int x1,int y1,int x2,int y2);

 int suan(int x1,int y1,int x2,int y2,int i1,int j1,int i2,int j2);

 int jdz(int x) {

     return x>?x:-x;

 }

 int main() {

     freopen("station.in","r",stdin);

     freopen("station.out","w",stdout);

     memset(f,-,sizeof f);

     for(int i=; i<=; i++)

         for(int j=; j<=; j++)

             cin>>mp[i][j];

     for(int i=; i<=; ++i)

         for(int j=; j<=; ++j)

             tu[i][j] = (mp[i][j]=='#');

     /*for(int i=1;i<=8;i++)

         {

             for(int j=1;j<=8;j++)

             cout<<tu[i][j]<<" ";

             cout<<"\n";

         }*/

     int ans=dfs(,,,);

     cout<<ans;

     fclose stdin;

     fclose stdout;

     return ;

 }

 int suan(int x1,int y1,int x2,int y2,int i1,int j1,int i2,int j2) {

     int sum=;

     for(int i=i1; i<=i2; i++)

         for(int j=j1; j<=j2; j++)

             sum+=(tu[i][j])*max(max(jdz(i-x1),jdz(i-x2)),max(jdz(j-y1),jdz(j-y2)));

     return sum;

 }

 int dfs(int x1,int y1,int x2,int y2) {

     if(x1>x2||y1>y2)return ;

     if(f[x1][y1][x2][y2]!=-) return f[x1][y1][x2][y2];

     int &res=f[x1][y1][x2][y2];

     res=suan(x1,y1,x2,y2,x1,y1,x1,y2)+dfs(x1+,y1,x2,y2);

     res=min(res,suan(x1,y1,x2,y2,x2,y1,x2,y2)+dfs(x1,y1,x2-,y2));

     res=min(res,suan(x1,y1,x2,y2,x1,y1,x2,y1)+dfs(x1,y1+,x2,y2));

     res=min(res,suan(x1,y1,x2,y2,x1,y2,x2,y2)+dfs(x1,y1,x2,y2-));

     return res;

 }