10分dfs求助
查看原帖
10分dfs求助
912779
isme1楼主2023/8/29 17:15
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,cnt=0; 
string s="hehe";
char a[10005][10005];
int l[10005],r[10005],w=0,len,kl=0;
void dfs(int x,int y,int f){
	if(f==len+1){
		cnt++;
		kl=0;
		return;
	}
	if(a[x-1][y]==s[f]&&(kl==0||kl==1)){
		f++;
		kl=1;
		dfs(x-1,y,f);
	}
	else if(a[x+1][y]==s[f]&&(kl==0||kl==2)){
		f++;
		kl=2;
		dfs(x+1,y,f);
	}
	else if(a[x][y+1]==s[f]&&(kl==0||kl==3)){
		f++;
		kl=3;
		dfs(x,y+1,f);
	}
	else if(a[x][y-1]==s[f]&&(kl==0||kl==4)){
		f++;
		kl=4;
		dfs(x,y-1,f);
	}
    else kl=0;

}
signed main()
{
    cin>>n>>m;
    len=s.size()-1;
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++){
    		cin>>a[i][j];
    		if(a[i][j]=='h'){
    			l[++w]=i;
    			r[w]=j;
    		}
    	}
    }
    for(int i=1;i<=w;i++){
    	dfs(l[i],r[i],1);
    }
    cout<<cnt;
	return 0;
}


2023/8/29 17:15
加载中...