C++回溯算法

迷宫的所有路径

#include<bits/stdc++.h>
using namespace std;
void func(int,int,int);
bool a[110][110];
int b[110];
int c[110];
int top=1;
int n;
int main()
{cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=true;b[0]=1;c[0]=1;a[1][1]=false;func(1,1,1);return 0;
}
void func(int x,int y,int s)
{int i,j;if(x==n&&y==n){cout<<top<<':';for(int l=0;l<s;l++){cout<<b[l]<<','<<c[l]<<"->";}cout<<b[s]<<','<<c[s]<<endl;top++;}//右i=x;j=y+1;if(i>=1&&i<=n&&j>=1&&j<=n&&a[i][j]==true){b[s]=i;c[s]=j;a[i][j]=false;func(i,j,s+1);a[i][j]=true;}//下 i=x+1;j=y;if(i>=1&&i<=n&&j>=1&&j<=n&&a[i][j]==true){b[s]=i;c[s]=j;a[i][j]=false;func(i,j,s+1);a[i][j]=true;}//左 i=x;j=y-1;if(i>=1&&i<=n&&j>=1&&j<=n&&a[i][j]==true){b[s]=i;c[s]=j;a[i][j]=false;func(i,j,s+1);a[i][j]=true;}//上 i=x-1;j=y;if(i>=1&&i<=n&&j>=1&&j<=n&&a[i][j]==true){b[s]=i;c[s]=j;a[i][j]=false;func(i,j,s+1);a[i][j]=true;}
}

 LETTERS

#include<bits/stdc++.h>
using namespace std;
void func(int,int,int);
char a[110][110];
int b[110];
int f=false;
int ma=-1;
int n,m;
int main()
{cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];}}func(0,0,1);cout<<ma;return 0;
}
void func(int x,int y,int cnt)
{b[(int)a[x][y]]=1;ma=max(ma,cnt);int i,j;//右i=x;j=y+1;if(i>=0&&i<n&&j>=0&&j<m&&b[(int)a[i][j]]==0){b[(int)a[i][j]]=1;func(i,j,cnt+1);b[(int)a[i][j]]=0;}//下 i=x+1;j=y;if(i>=0&&i<n&&j>=0&&j<m&&b[(int)a[i][j]]==0){b[(int)a[i][j]]=1;func(i,j,cnt+1);b[(int)a[i][j]]=0;}//左 i=x;j=y-1;if(i>=0&&i<n&&j>=0&&j<m&&b[(int)a[i][j]]==0){b[(int)a[i][j]]=1;func(i,j,cnt+1);b[(int)a[i][j]]=0;}//上 i=x-1;j=y;if(i>=0&&i<n&&j>=0&&j<m&&b[(int)a[i][j]]==0){b[(int)a[i][j]]=1;func(i,j,cnt+1);b[(int)a[i][j]]=0;}
}