我目前对动态规划还没有系统的学习过，所以说不上啥专业的术语，我的题解也是从别人的题解中受到了启发，然后加入了自己的理解。
其他几个解题报告有的的纯贴代码，有的题解看得不是很懂，我尽量用通俗易懂的方式展示自己的解题思路，希望能帮助到大家，同时也提升我自己。
最开始刷这道题的时候，状态不是很好，当时想着用穷举法试下运气。
穷举法比较简单,就是遍历每一块空地，求该空地的距离和，然后找出所有空地中距离和的最小值，我用的是PHP语言，反正穷举法是过不了，会超时（即使能过也没啥意思，毕竟没点技术含量）
后来简单的想了下，最小值的空地应该会靠近这些房子的几何上的中心点，所以当时就想着找到这个中心点，然后简单的把中心点以及中心点附近的空地都遍历一遍，找出这些点中的最优解。怀着试一试的心态，居然AC了，后面我自己都发现有边界的测试用例，说明牛客网的测试用例还是不全面。
有个大神也是类似的思路，他提出了“等势线“的概念，即中点是绝对的最优解，如果中点不能建，就以中点为中心，向外扩展一圈，找这一圈中的最优解，如果这一圈没空地，则继续再往外扩一圈。
我跟他的思路大体相同，只是还是没有在数学上得到证明，所以理论上有风险。
贴下AC的代码（该解决方案有问题）：
<?php
//调试开关，1为开启，开启则输出一些中间调试信息
define("DEBUG", 0);
/**
* 计算坐标(i1,j1)到坐标(i2,j2)的距离
* @param int $i1
* @param int $j1
* @param int $i2
* @param int $j2
*/
function getDistance($i1, $j1, $i2, $j2)
{
return abs($i1 - $i2) + abs($j1 - $j2);
}
/**
* 计算$i $j位置的空地到各个房子之间的距离和
* @param array $map 地图方阵阶数
* @param int $blankI 空地坐标i
* @param int $blankJ 空地坐标j
*/
function getDistanceSum($map, $blankI, $blankJ)
{
$sum = 0;
for ($i = 0; $i < count($map); $i++) {
for ($j = 0; $j < count($map[$i]); $j++) {
if ($map[$i][$j] === 1) {
$sum += getDistance($blankI, $blankJ, $i, $j);
}
}
}
return $sum;
}
fscanf(STDIN, "%d", $num);
$map = [];
for ($i = 0; $i < $num; $i++) {
$input = fgets(STDIN);
$map[$i] = explode(' ', $input);
}
//将数据类型转成整形，php是弱类型语言，担心留坑
for ($i = 0; $i < $num; $i++) {
for ($j = 0; $j < $num; $j++) {
$map[$i][$j] = intval($map[$i][$j]);
}
}
$shortDist = -1;//最小距离和
$houseCount = 0;
$sumI = 0;
$sumJ = 0;
for ($i = 0; $i < $num; $i++) {
for ($j = 0; $j < $num; $j++) {
/* if ($map[$i][$j] === 0) {
//计算当前位置的距离和
$distance = getDistanceSum($map, $i, $j);
if (constant('DEBUG') == 1) {
echo $i . " " . $j . ":" . $distance . "\n";
}
if ($distance < $shortDist || $shortDist === -1) {
$shortDist = $distance;
}
}*/
if ($map[$i][$j] === 1) {
$houseCount++;
$sumI += $i;
$sumJ += $j;
}
}
}
$averageI = intval($sumI / $houseCount);
$averageJ = intval($sumJ / $houseCount);
if (constant('DEBUG') == 1) {
echo 'average i is ' . $averageI . "\n";
echo 'average j is ' . $averageJ . "\n";
}
for ($i = $averageI - 1; $i <= $averageI + 1 && $i < $num; $i++) {
if ($i < 0) {
continue;
}
for ($j = $averageJ - 1; $j <= $averageJ + 1 && $j < $num; $j++) {
if ($j < 0) {
continue;
}
if ($map[$i][$j] === 0) {
//计算当前位置的距离和
$distance = getDistanceSum($map, $i, $j);
if (constant('DEBUG') == 1) {
echo $i . " " . $j . ":" . $distance . "\n";
}
if ($distance < $shortDist || $shortDist === -1) {
$shortDist = $distance;
}
}
if ($map[$i][$j] === 1) {
$houseCount++;
$sumI += $i;
$sumJ += $j;
}
}
}
echo $shortDist . "\n"; 大家看上面的代码，其实很不严谨，比如如果没有一座房子，应该会有除以0的边界，如果中心点附近都是房子，没有空地，也会无解。但是居然AC了。
虽然AC了，但是内心没有任何高兴，因为这样通过没任何收获，后面参看了其他几个大神给出的解题报告，加入自己的理解，整出了自己的解决方案。
穷举法之所以会超时是因为遍历所有空地时间复杂度是O(N2),计算每块空地的距离和时间复杂度又是O(N2)，所以总的时间复杂度变成了O(N2)XO(N2)=O(N4)。
优化思路是看能不能减少计算每块空地的距离和的时间复杂度，后面经过分析建立了这样的数学模型。
我们建立一个如上图所示的平面直角坐标系，坐标系的左上角为原点，房子或空地坐落在网格上。
我们假定在原点建立物流中转站（即使原点是房子也没关系，不影响计算），假设各个房子到原点的距离和是distance00（可以遍历所有点算出来，这一步省不了），那么在(1,0)坐标出建立中转站的距离和能否便捷的算出来呢。
我们分析发现，将物流中转站从坐标(0,0)迁移到坐标(0,1)时，纵坐标方向上的距离没有任何影响，但是对于横坐标方向的距离有影响，影响如下：
对于横坐标x<=0的房子来说，距离增加了1，对于x>0的房子来说，距离减小了1，因此（0，1）坐标处的距离和为distance00+(x<=0的房子数量)-(x>0的房子数量)，为了描述方便，
我们设房子的总数量为house，原点所在线及左边(x<=0)的房子的数量为a0,原点线右边(x>0)的房子总数为house-a0(左边房子数加右边房子数等于房子总数），
那么上面的公式就可以简化为：（0，1）坐标处的距离和为：distance00+a0-(house-a0)=distance+2*a0-house。
利用这个公式就是快速的计算出(0,1),(0,2)......(0,num)坐标的距离。
同样的道理，如果把物流中转站从坐标(0,0)迁移到坐标(1,0)时，假设y<=0的房子数量为b0，则（1，0）处坐标的距离和为：distance00+2*b0-house。
这样，我们只要能统计出a0,a1......anum,b0,b1......bnum的数据，然后计算出(0,0)位置的坐标距离和，就能快速计算出其他位置的距离和。
相对于穷举法，这种计算方式的时间复杂度是O(1)级别（就是四则运算）。
统计出a0,a1......anum,b0,b1......bnum的数据应该比较简单，建立两个辅助数组即可。
贴上代码：
<?php
/**
*调试开关，1为开启，开启则输出一些中间调试信息
*/
define("DEBUG", 0);
class Solution
{
/**
* @var array 地图方阵数据
*/
private $map = [];
/**
* @var array x轴的辅助数组，记录x<=i的房子的总数，对应解题报告中的ai
*/
private $xHelp = [];
/**
* @var array y轴的辅助数组，记录x<=j的房子的总数，对应解题报告中的bj
*/
private $yHelp = [];
/**
* @var array 各个位置的距离值
*/
private $distances = [];
/**
* @var int 正方形的边长
*/
private $num = 0;
/**
* @var int 房子数量，即矩阵中1的总数
*/
private $house = 0;
public function __construct()
{
$this->init();
$this->calDistances();
}
/**
* 初始化辅助数组
*/
private function initHelp()
{
for ($i = 0; $i < $this->num; $i++) {
$this->xHelp[$i] = [];
$this->yHelp[$i] = [];
for ($j = 0; $j < $this->num; $j++) {
$this->xHelp[$i][$j] = 0;
$this->yHelp[$i][$j] = 0;
}
}
}
/**
* 初始化距离和结果数组（各个点的结果）
*/
private function initDistances()
{
for ($i = 0; $i < $this->num; $i++) {
$this->distances[$i] = [];
for ($j = 0; $j < $this->num; $j++) {
$this->distances[$i][$j] = 0;
}
}
}
/**
*初始化
*/
private function init()
{
$this->getInput();
$this->initHelp();
$this->initDistances();
//将数据类型转成整形，php是弱类型语言，担心留坑
for ($i = 0; $i < $this->num; $i++) {
for ($j = 0; $j < $this->num; $j++) {
$this->map[$i][$j] = intval($this->map[$i][$j]);
if ($this->map[$i][$j] === 1) {
$this->house++;
$this->markXHelp($i);
$this->markYHelp($j);
}
}
}
}
/**
* 计算坐标(i1,j1)到坐标(i2,j2)的距离
* @param int $i1
* @param int $j1
* @param int $i2
* @param int $j2
*/
private function getDistance($i1, $j1, $i2, $j2)
{
return abs($i1 - $i2) + abs($j1 - $j2);
}
/**
* 计算$i $j位置区域到各个房子之间的距离和
* @param int $blankI 空地坐标i
* @param int $blankJ 空地坐标j
*/
private function getDistanceSum($blankI, $blankJ)
{
$sum = 0;
for ($i = 0; $i < $this->num; $i++) {
for ($j = 0; $j < $this->num; $j++) {
if ($this->map[$i][$j] === 1) {
$sum += $this->getDistance($blankI, $blankJ, $i, $j);
}
}
}
return $sum;
}
/**
* 如果X轴$i位置有房子，则xHelp数组大于等于位$houseI置的元素值都需要加1
* @param $houseI
*/
private function markXHelp($houseI)
{
for ($i = $houseI; $i < $this->num; $i++) {
for ($j = 0; $j < $this->num; $j++) {
$this->xHelp[$i][$j]++;
}
}
}
/**
* @param $houseJ
*/
private function markYHelp($houseJ)
{
for ($i = 0; $i < $this->num; $i++) {
for ($j = $houseJ; $j < $this->num; $j++) {
$this->yHelp[$i][$j]++;
}
}
}
/**
* 获取输入数据
*/
private function getInput()
{
fscanf(STDIN, "%d", $this->num);
for ($i = 0; $i < $this->num; $i++) {
$input = fgets(STDIN);
$this->map[$i] = explode(' ', $input);
}
}
/**
* 根据公式计算各个点的距离和，详见解题报告中公式的推导过程
*/
private function calDistances()
{
$this->distances[0][0] = $this->getDistanceSum(0, 0);
for ($i = 0; $i < $this->num; $i++) {
if ($i > 0) {
$this->distances[$i][0] = $this->distances[$i - 1][0] + 2 * $this->xHelp[$i - 1][0] - $this->house;
}
for ($j = 1; $j < $this->num; $j++) {
$this->distances[$i][$j] = $this->distances[$i][$j - 1] + 2 * $this->yHelp[$i][$j - 1] - $this->house;
}
}
}
/**
* 根据矩阵数据，计算最小的距离和
* @return int
*/
public function getMinDistSum()
{
$shortDist = -1;//最小距离和
for ($i = 0; $i < $this->num; $i++) {
for ($j = 0; $j < $this->num; $j++) {
if ($this->map[$i][$j] === 0) {
$distance = $this->distances[$i][$j];
if (constant('DEBUG') == 1) {
echo $i . " " . $j . ":" . $distance . "\n";
}
if ($distance < $shortDist || $shortDist === -1) {
$shortDist = $distance;
}
}
}
}
return $shortDist;
}
}
$solution = new Solution();
$minDistSum = $solution->getMinDistSum();
echo $minDistSum . "\n"; 再贴下我自己的几个测试用例： Input1: 5 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 1 1 1 1 Output1: 48 Input2: 5 1 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 1 1 1 Output2: 51 Input3: 4 0 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 Output3: 8 Input4: 7 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 Output4: 140 Input5: 7 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 1 1 Output5: 148
本人致力于编写通俗易懂的解题报告，如果对上面有任何没看明白的地方，请直接留言回复。我会尽我所能完善解题报告。
我建立了一个git仓库专门存放代码，以及测试用例等资料，仓库地址：https://github.com/S-Knight/nowcoder
如果你觉得本文对您有帮助，记得给我点赞哦，你们的点赞是我持续更新的动力。
京公网安备 11010502036488号