【題解】ZeroJudge b841: 104北二5.骨牌遊戲

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=b841
【解題想法】Backtracking

#include <iostream>
using namespace std;

int h, w, ans, g[10][10], use[10][10];

void f(int x, int y, int cnt){
    if (x == h && y == w){
        ans = max(ans, cnt);
        return;
    }
    int nx, ny;
    if (y == w){
        nx = x+1;
        ny = 1;
    }
    else{
        nx = x;
        ny = y+1;
    }
    f(nx, ny, cnt);
    if (use[x][y]) return;
    if (g[x][y] == g[x+1][y] && !use[x+1][y]){
        use[x+1][y] = 1;
        f(nx, ny, cnt+1);
        use[x+1][y] = 0;
    }
    if (g[x][y] == g[x][y+1] && !use[x][y+1]){
        use[x][y+1] = 1;
        f(nx, ny, cnt+1);
        use[x][y+1] = 0;
    }
}

int main() {
    cin >> h >> w;
    for (int i = 1; i <= h; i++){
        for (int j = 1; j <= w; j++){
            cin >> g[i][j];
        }
    }
    f(1, 1, 0);
    cout << ans << "\n";
}
分享本文 Share with friends