记搜80pts WA on #3,#8求调
查看原帖
记搜80pts WA on #3,#8求调
477821
toolong114514楼主2024/6/11 16:43
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
char s[1005];
char str[5005];
bool vst[505][1005];
bool res[505][1005];
int n,len=-1,tlen,ans,cnt;
queue<int> q;
bool dfs(int pos1,int pos2){
	if(vst[pos1][pos2]) return res[pos1][pos2];
	vst[pos1][pos2]=true;
	if(pos2==len) return res[pos1][pos2]=true;
	if(pos1==tlen) return res[pos1][pos2]=false;
	if(s[pos2]=='*') return res[pos1][pos2]=dfs(pos1+1,pos2)||dfs(pos1,pos2+1)||dfs(pos1+1,pos2+1);
	else if(s[pos2]=='?') return res[pos1][pos2]=dfs(pos1+1,pos2+1);
	else{
		if(s[pos2]==str[pos1]) return res[pos1][pos2]=dfs(pos1+1,pos2+1);
		else return res[pos1][pos2]=false;
	}
}
char sp[1005];
int main(){
	ios::sync_with_stdio(false);
	cin>>sp;
	int tl=strlen(sp);
	for(int i=0;i<tl;i++){
		if(i!=0&&sp[i]=='*'&&sp[i-1]=='*') continue;
		s[++len]=sp[i];
	}
	len++;
	cin>>n;
	ans=n;
	while(n--){
		memset(vst,false,sizeof(vst)); 
		memset(res,false,sizeof(res));
		cin>>str;
		tlen=strlen(str);
		bool flag=false;
		for(int i=0;i<tlen;i++){
			if(s[0]!='*'&&s[0]!='?'&&str[i]!=s[0]) continue;
			if(dfs(i,0)){
				ans--;
				break;
			}
		}
	}
	cout<<ans;
	return 0;
}
2024/6/11 16:43
加载中...