题意
有n个格子排成一行,两人轮流填,可填入"S"或"0",先得到"SOS"的人胜;如果全部填完也没有出现"SOS",则为平局。请判断是先手胜、后手胜还有平局。
分析
第一次知道,博弈题也能打表找规律。
简单地说就是,给DFS一个返回值,返回三个不同的值分别代表先手胜、后手胜和平局。
枚举当前填的格子,如果出现后手出现必败态,先手胜,直接返回;如果后手出现平局,则存在平局;否则,后手败。
(好像超内存了...问题不大
不难得出结论:
n<7,平局
n >=7,
奇数,必胜
偶数,n<=14平局,n>14必败。
#include<bits/stdc++.h>
using namespace std; int n; int main()
{
int T, kase = ;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
printf("Case #%d: ", ++kase);
if(n < ) printf("Draw\n");
else
{
if(n&) printf("Panda\n");
else
{
if(n <= ) printf("Draw\n");
else printf("Sheep\n");
}
}
}
return ;
}
参考链接:
1. https://blog.csdn.net/a54665sdgf/article/details/82291977
2. https://blog.csdn.net/qq_36424540/article/details/82910289