AcWing 8. 机器人塔
原题链接
简单
作者:
YMYS
,
2025-03-26 22:06:55
·河南
,
所有人可见
,
阅读 3
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 50;
int a,b;
char* cr[N];
int ct;
int succ;
bool test(int pa, int pb){
int i,j;
for(i = ct;i>0;i--){
for(j = 0;j<i;j++){
if(pa >= 0 && pb >= 0){
if(cr[i][j] == cr[i][j+1]){
cr[i-1][j] = 'A';
pa--;
}else{
cr[i-1][j] = 'B';
pb--;
}
}else{
for(i = ct;i>0;i--){
for(j = 0;j<i;j++){
cr[i-1][j] = 'o';
}
}
return 0;
}
}
}
for(i = ct;i>0;i--){
for(j = 0;j<i;j++){
cr[i-1][j] = 'o';
}
}
if(pa==0 && pb==0) return true;
else return false;
}
void dfs(int x, int y, int pos, int end)
{
if(pos > end){
if(test(x, y)){
succ++;
return;
}else{
return ;
}
}else{
if(x>=0 && y>=0){
cr[end][pos] = 'A';
dfs(x-1, y, pos+1, end);
cr[end][pos] = 'o';
cr[end][pos] = 'B';
dfs(x, y-1, pos+1, end);
cr[end][pos] = 'o';
}else{
return;
}
}
}
signed main()
{
cin>>a>>b;
int sum = a+b;
memset(cr, NULL, 50);
while(sum>0){
cr[ct] = new char[ct+2];
memset(cr[ct], 'o', ct+2);
sum -= (ct + 1);
ct++;
}
ct--;
dfs(a, b, 0, ct);
cout<<succ<<endl;
return 0;
}