菜鸟题解 HDU-1045 Fire Net

原题直达

https://vjudge.net/contest/582185#problem/K

题干

原题面
参考翻译

Suppose that we have a square city with straight streets. A map of a city is a square board with n rows and n columns, each representing a street or a piece of wall.

A blockhouse is a small castle that has four openings through which to shoot. The four openings are facing North, East, South, and West, respectively. There will be one machine gun shooting through each opening.

Here we assume that a bullet is so powerful that it can run across any distance and destroy a blockhouse on its way. On the other hand, a wall is so strongly built that can stop the bullets.

The goal is to place as many blockhouses in a city as possible so that no two can destroy each other. A configuration of blockhouses is legal provided that no two blockhouses are on the same horizontal row or vertical column in a map unless there is at least one wall separating them. In this problem we will consider small square cities (at most 4x4) that contain walls through which bullets cannot run through.

The following image shows five pictures of the same board. The first picture is the empty board, the second and third pictures show legal configurations, and the fourth and fifth pictures show illegal configurations. For this board, the maximum number of blockhouses in a legal configuration is 5; the second picture shows one way to do it, but there are several other ways.

Your task is to write a program that, given a description of a map, calculates the maximum number of blockhouses that can be placed in the city in a legal configuration.

Input

The input file contains one or more map descriptions, followed by a line containing the number 0 that signals the end of the file. Each map description begins with a line containing a positive integer n that is the size of the city; n will be at most 4. The next n lines each describe one row of the map, with a '.' indicating an open space and an uppercase 'X' indicating a wall. There are no spaces in the input file.

Output

For each test case, output one line containing the maximum number of blockhouses that can be placed in the city in a legal configuration.

假设我们有一个有笔直街道的方形城市。城市地图是一块正方形的棋盘，有n行n列，每列代表一条街道或一堵墙。

碉堡是一个小城堡，有四个开口，可以射击。四个开口分别面向北、东、南、西。每个洞口将有一挺机枪射击。

这里我们假设一颗子弹的威力非常大，它可以穿越任何距离，并在途中摧毁一个碉堡。另一方面，一堵坚固的墙可以阻挡子弹。

目标是在一个城市中放置尽可能多的碉堡，这样就不会有两个碉堡互相摧毁。碉堡的配置是合法的，除非有至少一堵墙将它们分开，否则在地图上没有两个碉堡在同一水平行或垂直柱上。在这个问题中，我们将考虑小型方形城市(最多4x4)，其中包含子弹无法穿过的墙壁。

下图是同一板的五张图片。第一张图为空板，第二、三张图为合法配置，第四、五张图为非法配置。对于这个棋盘，合法配置中的最大碉堡数量是5;第二张图展示了一种方法，但还有其他几种方法。

你的任务是编写一个程序，给定地图的描述，计算在合法配置下城市中可以放置的最大碉堡数量。

Input

输入文件包含一个或多个映射描述，后面跟着一行包含数字0的行，表示文件的结束。每张地图的描述都以一条包含正整数n的线开头，n代表城市的大小;N的最大值是4。接下来的n行每一行描述地图的一行，带一个'。’表示一个开放空间，大写的‘X’表示一堵墙。输入文件中没有空格。

Output

对于每个测试用例，输出一行，其中包含在合法配置中可以放置在城市中的最大数量的碉堡。

测试案例

Input

4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0

Output

题意与思路

惭愧，没想到怎么用分治解决，最后还是靠深度优先搜索。

题意为给出一个最大不超过 4x4 的正方形表格，表格中有两种值：. 和 X 分别代表 空地 和 墙，你需要在空地摆放尽可能多的碉堡，满足：

墙的位置不能摆放碉堡
除非被墙遮挡，否则同一行、同一列中只能摆放一个碉堡

求最多能摆放多少碉堡。

核心思想：采用深度优先搜索的思想，遍历表格——

到达右下角，更新最大碉堡数
判断当前位置 是否可以放置碉堡，如果可以，放置碉堡并记录数量，继续遍历，然后回溯

由于遍历的顺序是从左到右、从上到下，因此每次判断当前位置是否可以放置碉堡时，只需要查看它的上方和左侧是否有碉堡 即可。

代码表示：

void Traversal(int dep, int num){
    // dep - 深度
    // num - 当前碉堡数
    if(dep == n * n){  // 达到右下角，更新碉堡数
        num_b = max(num_b, num);
        return ;
    }
    int x = dep / n;  // 当前行数
    int y = dep % n;  // 当前列数
    if(city[x][y] == '.' && isLegal(x, y)){  // 当前坐标可以放置
        city[x][y] = 'b';  // 放置碉堡
        Traversal(dep + 1, num + 1);  // 继续遍历
        city[x][y] = '.';  // 回溯
    }
    Traversal(dep + 1, num);  // 不能放置碉堡   
}

题解

#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 10;

char city[maxn][maxn];

int n;
int num_b;

bool isLegal(int x, int y){
    for(int i = x - 1;i >= 0;i--){
        if(city[i][y] == 'b')  // 遇到碉堡
            return false;
        
        if(city[i][y] == 'X')  // 遇到墙
            break;  // 表明x方向上有墙遮挡，可以放置碉堡
    }

    for(int i = y - 1;i >= 0;i--){
        if(city[x][i] == 'b')  // 遇到碉堡
            return false;

        if(city[x][i] == 'X')  // 遇到墙
            break;  // 表明y方向上有墙遮挡，可以放置碉堡
    }
    return true;
}

void Traversal(int dep, int num){
    if(dep == n * n){
        num_b = max(num_b, num);
        return ;
    }
    int x = dep / n;
    int y = dep % n;
    if(city[x][y] == '.' && isLegal(x, y)){  // 当前坐标可以放置
        city[x][y] = 'b';  // 放置碉堡
        Traversal(dep + 1, num + 1);
        city[x][y] = '.';  // 回溯
    }
    Traversal(dep + 1, num);  // 不能放置碉堡   
}


int main(){
    while (scanf("%d", &n) != EOF && n){
        for(int i = 0;i < n;i++)
            cin>>city[i];
        num_b = 0;
        Traversal(0, 0);
        cout<<num_b<<endl;
    }
    return 0;
}