C++回溯算法

迷宫的所有路径

​
#include<bits/stdc++.h>
using namespace std;
void f(int,int),print();
int n,m;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
char a[100][100];
bool flag=false;
struct point{
	int x,y;
};
point r[10000];
int lr=0;
int main()
{
	system("color 1");
    cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
	    }
	}
	f(1,1);
	return 0;
}
 
void f(int x,int y){
	a[x][y]='o';
	r[lr].x=x;
	r[lr].y=y;
	lr++;
	if(x==n&&y==m){
		print();
		return;
	}
	for(int i=0;i<4;i++){
		int tx=x+dx[i];
		int ty=y+dy[i];
		if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]=='.'&&flag==false){
			a[tx][ty]='o';
			f(tx,ty);
			lr--;
			a[tx][ty]='.';
		}
	}
	
	return;
}
void print(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout<<setw(3)<<a[i][j];
		}
		cout<<endl;
	}
	for(int i=0;i<lr;i++){
		cout<<"("<<r[i].x<<","<<r[i].y<<") ";
	}
}
 
​

LETTERS

#include<bits/stdc++.h>
using namespace std;
void f(int,int,int);
int n,m,ma=0;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
char a[100][100];
bool flag=false,c[100];
struct point{
	int x,y;
};
point r[10000];
int lr=0;
int main()
{
	system("color 1");
    cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
	    }
	}
	f(1,1,1);
	cout<<ma;
	return 0;
}
 
void f(int x,int y,int cnt){
	c[(int)a[x][y]]=true;
	ma=max(ma,cnt);
	for(int i=0;i<4;i++){
		int tx=x+dx[i];
		int ty=y+dy[i];
		if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&c[(int)a[tx][ty]]==false){
			f(tx,ty,cnt+1);
			c[(int)a[tx][ty]]=false;
		}
	}
	
	return;
}

棋盘问题

#include<bits/stdc++.h>
using namespace std;
void f(int,int,int),print();
bool iif(int,int);
int n,m;
char a[100][100];
int sum=0;
int main()
{
	system("color 1");
	while(1){
		cin>>n>>m;
		if(n==-1&&m==-1) break;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				cin>>a[i][j];
			}
		}
		f(0,0,0);
		cout<<sum;
	}
	return 0;
}
 
void f(int x,int y,int cnt){
	if(cnt==m){
		sum++;
		return;
	}
	if(x==n){
		return;
	}
	for(int i=0;i<n;i++){
		if(iif(x,i)==true&&a[x][i]=='#'){
			a[x][i]='o';
			f(x+1,i,cnt+1);
			a[x][i]='#';
		}
	}
	
	return;
}
bool iif(int x,int y){
	for(int i=0;i<n;i++){
		if(a[x][i]=='o'&&i!=y) return false;
	}
	for(int i=0;i<n;i++){
		if(a[i][y]=='o'&&i!=x) return false;
	}
	return true;
}
void print(){
		cout<<"------------------------------------"<<endl;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cout<<a[i][j];
		}
		cout<<endl;
	}
}