比赛 20120323 评测结果 C
题目名称 加利福尼亚旅店 最终得分 0
用户昵称 恢复用户698 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-03-23 21:30:46
显示代码纯文本
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int	MAX_N	= 50 + 10;

int			N, M;
int			f		[MAX_N][MAX_N];
char		s1		[MAX_N];
char		s2		[MAX_N];

int DFS(int a, int b)
{
	if (f[a][b] >= 0) return f[a][b];
	if (a == N || b == M) {
		if (a == N && b == M) f[a][b] = 1;
		else f[a][b] = 0;
		return f[a][b];
	}
	if (s1[a] == '?') f[a][b] = DFS(a + 1, b + 1);
	else if (s1[a] == '*') 
		f[a][b] = DFS(a + 1, b + 1) || DFS(a + 1, b) || DFS(a, b + 1);
	else f[a][b] = s1[a] == s2[b] ? DFS(a + 1, b + 1) : 0;
	return f[a][b];
}

void Solve()
{
	int ans = 0;
	N = strlen(s1);
	int T; for(scanf("%d", &T); T --; ) {
		scanf("%s", s2); M = strlen(s2);
		memset(f, -1, sizeof f);
		if (DFS(0, 0)) ++ ans;
	}
	printf("%d\n", ans);
}

int main()
{
	freopen("hotela.in", "r", stdin);
	freopen("hotela.out", "w", stdout);
	while (scanf("%s", s1) == 1) Solve();
	return 0;
}