DFSするか,bit全探索でよい. どちらでも良い場合は,forで実装した方が簡単でミスも少なく, 計算量も良い.
注意
DFSする場合は,葉の部分に着いたときに答えを集計するが, return するときに v.pop_back() を忘れないこと.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
for, bit全探索
int main() {
ll h,w; cin>> h >> w;
vvll a(h, vll(w)); cinvv(a);
vll v;
ll ans = 0;
auto dfs = [&](auto dfs, ll x, ll y) -> void {
if(!in(x,h)) return ;
if(!in(y,w)) return ;
ll now = a[x][y];
v.push_back(now);
if(x == h-1 && y == w-1){
set<ll> tmp;
for(auto i: v){ tmp.insert(i); }
ans += v.size() == tmp.size();
v.pop_back(); // do not forget
return ;
}
dfs(dfs, x+1, y);
dfs(dfs, x, y+1);
v.pop_back();
return ;
};
dfs(dfs, 0,0);
cout << ans << endl;
return 0;
}
DFS
int main() {
ll h,w; cin >> h >> w;
vvll a(h,vll(w));
cinvv(a);
vll v;
ll ans = 0;
v.push_back(a[h-1][w-1]);
auto f = [&](auto f, ll x, ll y) -> void {
if(x == h-1 && y == w-1){
set<ll> tmp;
for(auto i: v){
tmp.insert(i);
}
if(v.size() == tmp.size()) ans ++;
return ;
}
ll now = a[x][y];
if(in(x+1, h)) f(f, x+1, y);
if(in(y+1,w)) f(f, x, y+1);
v.pop_back();
};
f(f, 0,0);
cout << ans << endl;
return 0;
}
*1:now