站外题WA求助,简单深搜
  • 板块灌水区
  • 楼主Nail9
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/12 22:58
  • 上次更新2024/4/13 09:56:28
查看原帖
站外题WA求助,简单深搜
1121118
Nail9楼主2024/4/12 22:58

题目图片

我的代码(AC:63.6%):

#include <bits/stdc++.h>
using namespace std;
const int MAX=10+9;
int datum[MAX][MAX];
bool visited[MAX][MAX];
vector<int> Asearch;
int nhang,mlie;

bool fsearch(int hang,int lie,int pnow){
	if(visited[hang][lie])
		return false;
	if(pnow==(int)Asearch.size()-1)
		return true;
	visited[hang][lie]=true;
	bool flag=false;
	
	if(datum[hang-1][lie]==Asearch[pnow+1]&&fsearch(hang-1,lie,pnow+1))
		flag=true;
	if(datum[hang+1][lie]==Asearch[pnow+1]&&fsearch(hang+1,lie,pnow+1))
		flag=true;
	if(datum[hang][lie-1]==Asearch[pnow+1]&&fsearch(hang,lie-1,pnow+1))
		flag=true;
	if(datum[hang][lie+1]==Asearch[pnow+1]&&fsearch(hang,lie+1,pnow+1))
		flag=true;
	
	if(flag)
		return true;
	else{
		visited[hang][lie]=false;
		return false;
	}
}

int main(){
	freopen("in.txt","r",stdin);
	scanf("%d %d",&nhang,&mlie);
	string tmpstr;//char tmpchar;
	getline(cin,tmpstr);//getchar();
	for(int i=1;i<=nhang;i++){
//		for(int j=1;j<=mlie;j++){
//			scanf("%c",&tmpchar);
//			datum[i][j]=tmpchar-'A'+1;
//		}
//		getchar();
		getline(cin,tmpstr);
		for(int j=0;j<mlie;j++){
			datum[i][j+1]=tmpstr[j]-'A'+1;
		}
	}
	getline(cin,tmpstr);
//	while(scanf("%c",&tmpchar)!=EOF){
//		Asearch.push_back(tmpchar-'A'+1);
//	}
	for(int i=0;i<(int)tmpstr.length();i++)
		Asearch.push_back(tmpstr[i]-'A'+1);
	
	for(int ihang=1;ihang<=nhang;ihang++)
		for(int ilie=1;ilie<=mlie;ilie++){
			if(datum[ihang][ilie]==Asearch.front()){
				if(fsearch(ihang,ilie,0)){
					printf("yes");
					return 0;
				}
			}
		}
	
	printf("no");
	return 0;
}
2024/4/12 22:58
加载中...