回溯算法(c++)

作者 : admin 本文共1036个字,预计阅读时间需要3分钟 发布时间: 2024-06-16 共1人阅读

回溯算法(c++)插图

#include 
#include 
using namespace std;
char b[110][110];
int n;
int cntt = 0;
int x[110],y[110];
int di[] = {0,1,0,-1};
int dj[] = {1,0,-1,0};
int cnt = 0;
void aaa(int,int);
int main()
{
	cin>>n;
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<n;j++)
		{
			b[i][j] = '.';
		}
	}
	
	aaa(0,0);
	return 0;
}
void aaa(int i,int j)
{
	b[i][j] = '#';
	x[cnt] = i;
	y[cnt] = j;
	cnt++;
	
	if(i==n-1&&j==n-1)
	{
		cntt++;
		cout<<cntt<<":";
		for(int ii = 0;ii<cnt-1;ii++)
		{
			cout<<x[ii]+1<<","<<y[ii]+1< ";
		}
		cout<<x[cnt-1]+1<<","<<y[cnt-1]+1<<endl;
		x[cnt-1] = 0;
		y[cnt-1] = 0;
		
		return;
	}
	for(int qqq = 0;qqq=0&&ti=0&&tj<n&&b[ti][tj]=='.')
		{
			b[ti][tj] = '#';
			aaa(ti,tj);
			cnt--;
			b[ti][tj] = '.';
		}
	}
	
	return;
}

回溯算法(c++)插图(1)

#include 
#include 
using namespace std;
char b[110][110];
int n,m;
bool f = false;
int ma = -99999;

int di[] = {0,1,0,-1};
int dj[] = {1,0,-1,0};
int c[100];
void aaa(int,int,int);
int main()
{
	cin>>n>>m;
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j>b[i][j];
		}
	}
	
	aaa(0,0,1);
	cout<<ma;
	return 0;
}
void aaa(int i,int j,int cnt)
{
	c[(int)b[i][j]] = 1;
	ma = max(ma,cnt);
	for(int qqq = 0;qqq=0&&ti=0&&tj<m&&c[(int)b[ti][tj]]==0)
		{
			c[(int)b[ti][tj]] = 1;
			aaa(ti,tj,cnt+1);
			
			c[(int)b[ti][tj]] = 0;
		}
	}
	
	return;
}

本站无任何商业行为
个人在线分享 » 回溯算法(c++)
E-->