昨天在寢室寫(xiě)的1154還是比較簡(jiǎn)單的DFS,開(kāi)始的時(shí)候忘記了路徑的復(fù)原，還有就識(shí)要注意一下，最開(kāi)始的點(diǎn)要標(biāo)記。
代碼：
#include<iostream>
#include<stdio.h>
#define MAXN 20
using namespace std;
int DFS(int i,int j,int len,int r,int c);
bool key[26];
char a[MAXN][MAXN];
int main()
{
int i;
int j;
int r;
int c;
cin>>r>>c;
for(i = 0; i < r; ++ i)
{
for(j = 0; j < c; ++ j)
{
cin>>a[i][j];
}
}
key[a[0][0]-'A'] = true;
cout<<DFS(0,0,1,r,c)<<endl;
}
int DFS(int i,int j,int len,int r,int c)
{
int tem;
tem = len;
int max = 0;
if(i > 0)
{
if(!key[a[i-1][j] - 'A'])
{
key[a[i-1][j] - 'A'] = true;
len = DFS(i-1,j,len+1,r,c);
key[a[i-1][j] - 'A'] = false;
if(len > max)
max = len;
len = tem;
}
}
if(i < r-1)
{
if(!key[a[i+1][j] - 'A'])
{
key[a[i+1][j] - 'A'] = true;
len = DFS(i+1,j,len+1,r,c);
key[a[i+1][j] - 'A'] = false;
if(len > max)
max = len;
len = tem;
}
}
if(j > 0)
{
if(!key[a[i][j-1] - 'A'])
{
key[a[i][j-1] - 'A'] = true;
len = DFS(i,j-1,len+1,r,c);
key[a[i][j-1] - 'A'] = false;
if(len>max)
max = len;
len = tem;
}
}
if(j < c-1)
{
if(!key[a[i][j+1] - 'A'])
{
key[a[i][j+1] - 'A'] = true;
len = DFS(i,j+1,len+1,r,c);
key[a[i][j+1] - 'A'] = false;
if(len>max)
max = len;
len = tem;
}
}
if(len > max)
max = len;
return max;
}