洛谷U423720题解

题解

方法一四重循环

枚举这个四位数的四位 $abcd$，最后检查是否符合要求
若符合，计数器加一
代码比较简单，我就不写了

方法二dfs递归

dfs很简单，没学过的学一下

代码

#include <bits/stdc++.h>
using namespace std;
char c;
int flag[15],a[10];
int cnt = 0;
void dfs(int step)
{
	if(step > 4)
	{
		bool check = true;
		for(int i = 0;i <= 9;i++)
		{
			if(flag[i] == 1)
			{
				bool flag = false;
				for(int j = 1;j <= 4;j++)
				{
					if(a[j] == i)	flag = true;
				}
				if(!flag)
				{
					check = false;
					break;
				}
			}
			else if(flag[i] == -1)
			{
				bool flag = false;
				for(int j = 1;j <= 4;j++)
				{
					if(a[j] == i)	flag = true;
				}
				if(flag)
				{
					check = false;
					break;
				}
			}
		}
		if(check)	cnt++;
		return;
	}
	for(int i = 0;i <= 9;i++)
	{
		a[step] = i;
		dfs(step + 1);
	}
}
int main()
{
	for(int i = 0;i <= 9;i++)
	{
		cin >> c;
		if(c == 'o')	flag[i] = 1;
		if(c == 'x')	flag[i] = -1;
	}
	dfs(1);
	cout << cnt << endl;
	return 0;
}