一种单人玩的游戏，规则为：
在一个R行C列的方格上，每个方格中有一个A-Z的字母。游戏从左上角（第一行，第一列）位置开始，一步一步地向相邻（上、下、左、右）方格移动。唯一的限制是路径上的方格中的字母，每种字母只能出现1次。
游戏的目标是走尽可能长的路径。请你写程序算出指定棋盘上，可能走的最长步数。
第一行有两个以空格分开的两个整数R和C，1≤R，C≤20。
后面R行每行有C个字母，每行表示棋盘上的一行状态。
有且只有一行，你计算出的最长步数。
2 4 CAAB ADCB
3
3 6 HFDFFB AJHGDH DGAGEH
6
5 5 IEFCJ FHFKC FFALF HFGCF HMCHH
10
思路：一步一步往下搜，记得回溯步数。
#include<iostream> #include<string> using namespace std; int n,m,t,ans; char a[21][21]; bool g[27]; void dfs(int w,int x) { if(w-1>0&&!g[a[w-1][x]-64]){g[a[w-1][x]-64]=1;t++;dfs(w-1,x);t--;g[a[w-1][x]-64]=0;} if(x-1>0&&!g[a[w][x-1]-64]){g[a[w][x-1]-64]=1;t++;dfs(w,x-1);t--;g[a[w][x-1]-64]=0;} if(w+1<=n&&!g[a[w+1][x]-64]){g[a[w+1][x]-64]=1;t++;dfs(w+1,x);t--;g[a[w+1][x]-64]=0;} if(x+1<=m&&!g[a[w][x+1]-64]){g[a[w][x+1]-64]=1;t++;dfs(w,x+1);t--;g[a[w][x+1]-64]=0;} ans=max(ans,t); return; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)cin>>a[i][j]; g[a[1][1]-64]=1; dfs(1,1); cout<<ans+1; return 0; }
原文：https://www.cnblogs.com/2006hanziwei/p/10744128.html