エンジニアが死滅シタ世界体验（四）

QQ截图20190124163901.jpg
上一篇（https://iobaka.com/blog/88.html）文章解决了该游戏 B 难度下的地区问题，这一篇开始解决难度 A 的问题。

上手

问题1：有名なプールサイド [MISSION LEVEL: A]

あなたは今度新しくできる町のデザインを任されました。
町は南北に H、東西に W の広さで、計 H × W 個の区画からなっています。
また、それぞれの区画には、次の図のように座標が割り当てられているものとします。

町に建設したい建物のリストが与えられます。
どの建物も長方形の形をしており、ただ一つの扉を持っています。

リストにはたくさんの建物が含まれているため、リストに載っている全ての建物を建設することができるとは限りません。
そこで、町のどこにどの建物を建設するかを決めるのがあなたの仕事です。
建物を建設する場所を決める際には、次の 3 つのルールを守らなくてはいけません。
どの 2 つの建物も重なってはいけない。
建設する建物の向きはリストに与えられたとおりでないといけない (建物を回転して配置してはいけない)。
どの 2 つの建物についても、それらの扉の間を「建物がない区画」を通って移動できる。
ルール 3 を正確に述べると、次のようになります：すべての建設する建物の組に対して、それらの扉の座標を P, Q とするとき、
以下の条件 (i)-(iii) を満たすような座標の列 (r_1, c_1), (r_2, c_2), ..., (r_m, c_m)
が存在する (m は 0 以上の整数)。
(i) 1 ≦ r_i ≦ H, 1 ≦ c_i ≦ W が成り立つ (1 ≦ i ≦ m)。
(ii) 座標 (r_i, c_i) にはどの建物も建設されていない (1 ≦ i ≦ m)。
(iii) 座標 (r_i, c_i) と (r_{i+1}, c_{i+1}) は上下左右のいずれかで隣接している (0 ≦ i ≦ m)。ただし、P = (r_0, c_0), Q = (r_{m+1}, c_{m+1}) とする。
次の図は条件 (i)-(iii) が守られている建物の配置と守られていない配置の例を表しています。
灰色の建物と緑の建物については、それらの扉の間を「建物がない区画」を通って移動することができます。
一方、灰色の建物と青の建物については、そのような移動方法は存在しません。

町の区画 X 個分の大きさの建物は、X 万円の利益を生み出します。
建物が生み出す利益の合計ができるだけ多くなるような、建物の配置を求めるプログラムを書いてください。
最低1個以上の利益を生み出す建物を配置することで正解となり、建物の面積がスコアとして計算されます。

解释：
你这次开始设计村庄规划了。
村庄南北向为 H ，东西向为 W ，总计 H × W 个格子。
假设给每个格子分配一个坐标，就如图1所示。

然后会列给你一个村庄建筑清单。
每栋建筑物都是矩形形状，并且有一个门。
门的位置不会是矩形的四个顶点。
就如图2所示。

由于建筑清单里有很多建筑物，所以并不是所有建筑全部都能建造在村子里。
所以你需要决定村子里需要建哪些建筑。

在决定建筑物的建筑地点时，需要遵守以下3点：
1.任何两个建筑物，不允许重叠
2.建筑物建筑方向需要和清单里给的一样，不许旋转放置建筑物。
3.任何两个建筑物，可以通过没有建筑的方块，和建筑物的门之间移动。

规则3如图3所示，
灰色建筑物和绿色建筑物之间，可以通过没有建筑的方块，以两个建筑物的门为起点和终点，进行移动。
而蓝色建筑物，则和其他两个建筑物之间没有移动方法，所以蓝色建筑物不满足规则3。

这个村子每个格子的建筑物可以产生1万日元的利润，
请编写一个程序，计算建筑物的放置位置，尽可能多的产生利润。

至少放置一个能产生利润的建筑物，就判定为正确答案，并根据利润计算得分。
（需要注意的是：1.建筑的门前至少有一个格子 2.建筑的门不会在建筑的四个顶点位置）

解答：
这道题要求是尽可能产生最多的利润，但是只要至少放置一个建筑物，就算为过关。
所以思路是，先创建一个二维数组，画出整个村庄，用0标识没有建筑的空格子。
然后创建个数组依次存入每栋建筑的长、宽以及门的坐标。

然后循环遍历建筑物，找出符合建造条件的建筑，放到村庄里，输出结果即可。
要找出符合条件的建筑需要以下几个条件：
1.建筑物的高度要小于或等于村庄总高度。
2.建筑物的宽度要小于或等于村庄总宽度。
3.如果门在建筑物的最左侧或最右侧，则建筑物的宽度要小于村庄总宽度。
4.如果门在建筑物的最顶排或最底排，则建筑物的高度要小于村庄总高度。

用以上四条规则，就可以筛选出符合建造规范的建筑。
但是筛选出来之后，不能直接在村庄上建造，需要对建筑进行偏移。
比如建筑物为 3(H)*4(W)，门在最顶排时，输出需要为：
0 0 0 0 0
1 1 1 1 0
1 1 1 1 0
1 1 1 1 0
来保证门的正前方是空地。
同理，门在最左侧时，输出则需要为：
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 0 0 0 0
最后程序如下：

<?php
    // 自分の得意な言語で
    // Let's チャレンジ！！

    $input_lines = fgets(STDIN);
    $input_lines = explode(' ', $input_lines);
    $area = [];
    // 绘制村庄地图
    for ($j = 0; $j < $input_lines[0]; $j++) {
         for ($k = 0; $k < $input_lines[1]; $k++) {
              $area[$j][$k] = 0;
         }
    }
    // 存放建筑清单
    $build = [];
    for ($i = 0; $i < $input_lines['2']; $i++) {
        $data = fgets(STDIN);
        $data = explode(' ', $data);
        $build[$i]['height'] = $data[0];
        $build[$i]['width'] = $data[1];
        $build[$i]['door_x'] = $data[3];
        $build[$i]['door_y'] = $data[2];
        $build[$i]['build_id'] = $i+1;
    }
    // 循环筛选建筑物
    foreach ($build as $v) {
        // 坐标偏移量
        $y = 0;
        $x = 0;
        // 建筑物的高度及宽度要小于或等于村庄总高度及总宽度
        if($v['height'] <= $input_lines[0] && $v['width'] <= $input_lines[1]) {
            // 如果门在建筑物的最顶排或最底排，则建筑物的高度要小于村庄总高度
            if(($v['door_x'] == 1 || $v['door_x'] == $input_lines[1]-1) && $v['width'] == $input_lines[1]) {
                continue;
            }
            // 如果门在建筑物的最左侧或最右侧，则建筑物的宽度要小于村庄总宽度
            if(($v['door_y'] == 1 || $v['door_y'] == $input_lines[0]-1) && $v['height'] == $input_lines[0]) {
                continue;
            }
            // 如果门在最顶排，建筑物则向下偏移1格
            if($v['door_x'] == 1) {
                $y = 1;
            }
            // 如果门在最左侧，建筑物则向右偏移1格
            if($v['door_y'] == 1) {
                $x = 1;
            }
            // 将该建筑物绘制到村庄中
            for ($m = 0; $m < $v['height']; $m++) {
                 for ($n = 0; $n < $v['width']; $n++) {
                      $area[$m+$x][$n+$y] = $v['build_id'];
                 }
            }
            break;
        }
    }
    // 输出村庄建筑设计图
    for ($j = 0; $j < $input_lines[0]; $j++) {
        for ($k = 0; $k < $input_lines[1]; $k++) {
            if($k == $input_lines[1]-1) {
                echo $area[$j][$k];
            }     
            else {
                echo $area[$j][$k].' ';
            }
        }
        echo PHP_EOL;
    }
    
?>