【題目敘述】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";
}