《LETTER》一道深搜的题目 总是错一个
  • 板块学术版
  • 楼主魏老师
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/7/14 20:07
  • 上次更新2024/7/14 21:28:55
查看原帖
《LETTER》一道深搜的题目 总是错一个
285961
魏老师楼主2024/7/14 20:07


#include<bits/stdc++.h>
using namespace std;
int r,s,t,a[30][30],b[200],maxn=-1;//R是行数S是列数 
char ms[30][30];

void dfs(int i,int j) //i行j列 
{
	
	//上
	if(i-1>0&&a[i-1][j]==0)
	{
		if(b[ms[i-1][j]]==1)//到达 
		{
			//最大值算法 
			if(t>maxn) maxn=t;
		}
		else 
		{
			a[i-1][j]=1;
	        b[ms[i-1][j]]=1;
	        t++;
			dfs(i-1,j);
			a[i-1][j]=0;
	    	b[ms[i-1][j]]=0;
	    	t--;
		}
		
	} 
		
	//下
	if(i+1<=r&&a[i+1][j]==0)
	{
		if(b[ms[i+1][j]]==1)//到达 
		{
			//最大值算法 
			if(t>maxn) maxn=t;
		}
		else
		{
			a[i+1][j]=1;
	        b[ms[i+1][j]]=1;
	        t++;
			dfs(i+1,j);
			a[i+1][j]=0;
	    	b[ms[i+1][j]]=0;
	    	t--;
		} 
		
	}   
	
	//左
	if(j-1>0&&a[i][j-1]==0)
	{
		if(b[ms[i][j-1]]==1)//到达 
		{
			//最大值算法 
			if(t>maxn) maxn=t;
		}
		else 
		{
			a[i][j-1]=1;
	        b[ms[i][j-1]]=1;
	        t++;
			dfs(i,j-1);
			a[i][j-1]=0;
	    	b[ms[i][j-1]]=0;
	    	t--;
		}
		
	}   
	//右
	if(j+1<=s&&a[i][j+1]==0) 
	{
		if(b[ms[i][j+1]]==1)//到达 
		{
			//最大值算法 
			if(t>maxn) maxn=t;
		}
		else
		{
			a[i][j+1]=1;
	        b[ms[i][j+1]]=1;
	        t++;
			dfs(i,j+1);
			a[i][j+1]=0;
	    	b[ms[i][j+1]]=0;
	    	t--;	
		} 
		
	} 
}
int main()//主函数 
{
	cin>>r>>s;
	for(int i=1;i<=r;i++)
		for(int j=1;j<=s;j++)
			cin>>ms[i][j];
			
	
    a[1][1]=1;
	b[ms[1][1]]=1;	
	t=1;
	dfs(1,1);//从1行1列开始搜 
	cout<<maxn; 
	return 0;
}
2024/7/14 20:07
加载中...