【模拟】【递归】【dfs】恐怖的奴隶主

本文主要是介绍【模拟】【递归】【dfs】恐怖的奴隶主，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

恐怖的奴隶主

题目大意：

有4个bigbob（我们简称BB），每个BB有自己的初始血量（最大为k），当某个BB死后，其他受伤的BB会在最左边的空格召唤一个最大血量为s[t]的BB（t为当前受伤BB的血量），现在小明可以发动魔法，从左到右依次对每个BB造成一点伤害，现在小明发现某种情况下回有循环，现在问有那些情况是在循环中的

输入样例

2 
2

输出样例

样例解释

Bigbob最多有2血，满血bigbob受伤会召出新的。
循环的初始状态有：
(2,1,0,0),(1,2,0,0),(2,0,1,0),(2,1,1,0),(0,2,1,0),(1,2,1,0),(2,2,1,0) ,(1,0,2,0),(0,1,2,0),(1,1,2,0),(2,1,2,0),(2,1,0,1),(0,2,0,1),(1,2,0,1),(0,2,1,1),(1,2,1,1),(0,0,2,1),(1,0,2,1),(0,1,2,1),(1,1,2,1),(2,1,2,1),(0,2,2,1),(1,2,2,1),(2,1,0,2) ,(1,2,0,2),(2,0,1,2),(2,1,1,2),(0,2,1,2),(1,2,1,2),(2,2,1,2),(2,1,2,2)
共31种。

数据范围

对于30%的数据，k≤5；
对于70%的数据，k≤10, a[i]=k；
对于100%的数据，k≤15, 1≤a[i]≤k。

解题思路：

先dfs枚举出所有情况，然后模拟一下，判断是不是在循环中就可以了

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int k,ans,z[10],s[20],p[20][20][20][20],num[20][20][20][20];
void st(int aa,int bb,int cc,int dd)
{if(p[aa][bb][cc][dd]) return;//到过了p[aa][bb][cc][dd]=1;//记录int a=aa,b=bb,c=cc,d=dd;bool pp=false;//模拟if (a==1) pp=true;a=max(a-1,0);//-1if (a)//只是受伤if (!b) b=s[a];//找位置建BBelse if (!c) c=s[a];else if (!d) d=s[a];if (b==1) pp=true;b=max(b-1,0);if (b)if (!a) a=s[b];else if (!c) c=s[b];else if (!d) d=s[b];if (c==1) pp=true;c=max(c-1,0);if (c)if (!a) a=s[c];else if (!b) b=s[c];else if (!d) d=s[c];if (d==1) pp=true;d=max(d-1,0);if (d)if (!a) a=s[d];else if (!b) b=s[d];else if (!c) c=s[d];if(a+b+c+d==0||!pp)//判断是否结束了，或不在循环中{num[aa][bb][cc][dd]=2;//记录return;}st(a,b,c,d);if (num[a][b][c][d]==2) num[aa][bb][cc][dd]=2;//递归返回值else num[aa][bb][cc][dd]=1;
}
void dfs(int dep)
{if (dep>4){if (z[1]!=z[2]||z[2]!=z[3]||z[3]!=z[4]) st(z[1],z[2],z[3],z[4]);if (num[z[1]][z[2]][z[3]][z[4]]==1) ans++;return;}for (int i=0;i<=k;++i){z[dep]=i;//枚举每个位置dfs(dep+1);}
}
int main()
{scanf("%d",&k);for (int i=1;i<k;++i)scanf("%d",&s[i]);dfs(1);printf("%d",ans);//输出
}