【題解】ZeroJudge c780: 106北二5.炮打眾卒遊戲

題目敘述https://zerojudge.tw/ShowProblem?problemid=c780
解題想法:DFS + Backtracking

#include <iostream>
using namespace std;

int n, m, maxi, a[9][9];

void func(int x, int y, int steps){
    int count = 0;
    bool flag = false;
    for (int i = x+1; i < n; i++){
        if (a[i][y] == 1) count++;
        if (count == 2){
            a[i][y] = 0;
            func(i, y, steps+1);
            a[i][y] = 1;
            break;
        }
    }
    if (count >= 2) flag = true;
    count = 0;
    for (int i = x-1; i >= 0; i--){
        if (a[i][y] == 1) count++;
        if (count == 2){
            a[i][y] = 0;
            func(i, y, steps+1);
            a[i][y] = 1;
            break;
        }
    }
    if (count >= 2) flag = true;
    count = 0;
    for (int i = y+1; i < m; i++){
        if (a[x][i] == 1) count++;
        if (count == 2){
            a[x][i] = 0;
            func(x, i, steps+1);
            a[x][i] = 1;
            break;
        }
    }
    if (count >= 2) flag = true;
    count = 0;
    for (int i = y-1; i >= 0; i--){
        if (a[x][i] == 1) count++;
        if (count == 2){
            a[x][i] = 0;
            func(x, i, steps+1);
            a[x][i] = 1;
            break;
        }
    }
    if (count >= 2) flag = true;
    if (!flag && steps > maxi) maxi = steps;
}

int main(){
    while (cin >> n >> m){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                a[i][j] = 1;
            }
        }
        a[0][0] = 0;
        maxi = 0;
        func(0, 0, 0);
        cout << maxi << "\n";
    }
}
分享本文 Share with friends