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

题目描述

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.
http://acm.hdu.edu.cn/data/images/1045-1.jpg

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.

思路

这题是贪心算法,可我只会搜索。。。还是参考别人的代码。。

对每个格子搜索,一旦在空地放碉堡,就在在空地十字方向用F标记,直到遇到墙位置,然后在此状态下继续搜索。

直到所有格子都没有空位为止,停止搜索,回溯。

AC代码

/*************************************************************************
    > File Name: 1045.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-06-09 Tue 16:25:52 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;


int n;
char Map[4][4];

bool yes(char Map[4][4]) { // 判断是否搜索结束
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if(Map[i][j] == '.') // 还有空地则搜索未结束
                return false;
    return true; // 搜索结束
}

int DFS(char t[4][4]) {
    int maxbh=0;
    if(yes(Map)) 
        return 0; // 搜索结束,回溯。 
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            if(t[i][j] != '.') // 若不是空地,搜索下一格
                continue;
            char tt[4][4]; // 下一个状态
            memcpy(tt, t, sizeof(tt)); // 复制当前状态给下一个状态
            for(int x=i; x<n && t[x][j]!='X' ; ++x) // 用火力'F'标记列,直到遇到墙位置
                tt[x][j] = 'F';
            for(int x=i; x>=0 && t[x][j]!='X' ; --x)
                tt[x][j] = 'F';
            for(int y=j; y<n && t[i][y] != 'X'; ++y) // 用火力'F'标记行,直到遇到墙位置
                tt[i][y] = 'F';
            for(int y=j; y>=0 && t[i][y] != 'X'; --y)
                tt[i][y] = 'F';
            int bh = DFS(tt) + 1; // 再次基础上搜索下一个状态
            maxbh = max(maxbh, bh);
        }
    return maxbh;
}

int main()
{
#ifdef Oj
    freopen("1045.in", "r", stdin);
#endif
    while(cin >> n && n) {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                cin >> Map[i][j];
        char t[4][4];
        memcpy(t, Map, sizeof(Map));
        cout << DFS(t) << endl;
    }
    return 0;
}