HDU4499 Canon 爆搜DFS题解

原题

Problem Description

In Chinese Chess, there is one kind of powerful chessmen called Cannon. It can move horizontally or vertically along the chess grid. At each move, it can either simply move to another empty cell in the same line without any other chessman along the route or perform an eat action. The eat action, however, is the main concern in this problem.

An eat action, for example, Cannon A eating chessman B, requires two conditions:

1、A and B is in either the same row or the same column in the chess grid.

2、There is exactly one chessman between A and B.

Here comes the problem.

Given an N x M chess grid, with some existing chessmen on it, you need put maximum cannon pieces into the grid, satisfying that any two cannons are not able to eat each other. It is worth nothing that we only account the cannon pieces you put in the grid, and no two pieces shares the same cell.

Input

There are multiple test cases.

In each test case, there are three positive integers N, M and Q (1<= N, M<=5, 0<=Q <= N x M) in the first line, indicating the row number, column number of the grid, and the number of the existing chessmen.

In the second line, there are Q pairs of integers. Each pair of integers X, Y indicates the row index and the column index of the piece. Row indexes are numbered from 0 to N-1, and column indexes are numbered from 0 to M-1. It guarantees no pieces share the same cell.

Output

There is only one line for each test case, containing the maximum number of cannons.

Sample Input

4 4 2 
1 1 1 2 
5 5 8 
0 0 1 0 1 1 2 0 2 3 3 1 3 2 4 0       

Sample Output

8
9      

题目翻译

Problem Description

在中国象棋中，有一种棋子叫Canon。它可以沿棋盘水平或竖直方向直移动。在每次移动中，它可以简单地移动到同一行或同一列列中的另一个空单元格，而不需要沿途有任何其他棋子，也可以执行eat操作。我们需要特别关注这个eat操作

想要执行eat动作，例如，我们有Canon棋子 A 和普通棋子 B，需要两个条件：

1、A 和 B 位于国际象棋网格中的同一行或同一列中。

2、A和B之间正好有一个棋子。

问题来了。

给定一个N×M象棋网格，上面有一些现有的棋子，你需要在网格中放置最大数量的Canon，以满足任何两个Canon都不能互相吃掉的要求。我们只计算你放在格子里的Canon棋子，没有两个棋子可以共享同一个格子。

Input

多组输入；

在每个测试用例中，第一行中有三个正整数N、M和Q（1<=N、M<=5、0<=Q<=25），表示网格的行号、列号和现有棋子的数目。

在第二行，有Q对整数。每对整数X，Y表示棋子的横纵坐标。横坐标的编号从0到N-1，纵坐标的编号从0到M-1。它保证了没有棋子位于同一个单元格。

Output

放置Canon数量的最大值

题目分析

简单转述一下题目，一个给定大小的棋盘，已经放置好了Q个棋子，现在要在棋盘放尽可能多的的大炮，且任意两个炮吃不掉对方。

A棋子便是炮，B棋子便是炮架，下文章我们约定以此称呼。

我们来画图分析一下何为题目所述的合法状态/非法状态：

右侧展示的是本题的一个坑：两个炮之间隔三个棋-本题的隐含要求是走一步，因此两个炮隔三个棋不算相互吃掉，不需要特判这种情况。其次，炮可以当炮架。

那么搜索的思路如何？

首先，大框架上以行列为索引，逐行线性搜索，列扫描到右边界换行，行扫描到下边界搜索结束。

搜索过程中:

• 如果搜到棋子占格，那么继续线性搜索。

• 如果空位，分别对行列进行扫描，扫描到合法(符合题述条件)，放炮；扫描到非法(已经有炮和炮架)，则返回

  对于扫描到合法的情况，因为当前的合法状态未必能走到底，存在多种可能的情况，需要逐个情况进行尝试，因此需要回溯，即撤炮(恢复现场，出栈向上层返回)

AC Code

#include <bits/stdc++.h>
using namespace std;
int g[6][6], ans = 0;
int n, m, q;

void dfs(int x, int y, int cnt){
    if(x >= n){                                        //行扫描结束，搜索完成，更新最大值
        ans = max(ans, cnt);
        return;
    }
    if(y >= m){                                    //列扫描结束，换行继续扫描
        dfs(x + 1, 0, cnt);
        return;
    }
    if(g[x][y] == 1){                        //棋子占位，向后搜
        dfs(x, y + 1, cnt);
        return;
    }
    dfs(x, y + 1, cnt);
    bool flag = true;
    int t;
    //行扫描，检索炮和炮架
    for(t = x - 1; t >= 0; t--) if(g[t][y]) break;
    for(int i = t - 1; i >= 0; i--)
        if(g[i][y]){
            if(g[i][y] == 2) flag = false;
            break;
        }
    if(!flag) return;
    //列扫描，检索炮和炮架
    for(t = y - 1; t >= 0; t--) if(g[x][t]) break;
    for(int j = t - 1; j  >= 0; j--)
        if(g[x][j]){
            if(g[x][j] == 2) flag = false;
            break;
        }
    if(!flag) return;
    g[x][y] = 2;
    dfs(x, y + 1, cnt + 1);
    g[x][y] = 0;
}

int main(){
    while(cin >> n >> m >> q, n, m, q){
        memset(g, 0, sizeof(g));
        ans = 0;
        for(int i = 0; i < q; i++){
            int x, y;
            cin >> x >> y;
            g[x][y] = 1;
        }
        dfs(0, 0, 0); 
        cout << ans << endl;
    }
    return 0;
}