昨天在寝室写的1154还是比较简单的DFS,开始的时候忘记了路径的复原,还有就识要注意一下,最开始的点要标记。
代码:
#include<iostream>
#include<stdio.h>
#define MAXN 20
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int DFS(int i,int j,int len,int r,int c);
bool key[26];
char a[MAXN][MAXN];
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i;
int j;
int r;
int c;
cin>>r>>c;
for(i = 0; i < r; ++ i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(j = 0; j < c; ++ j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cin>>a[i][j];
}
}
key[a[0][0]-'A'] = true;
cout<<DFS(0,0,1,r,c)<<endl;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int DFS(int i,int j,int len,int r,int c)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int tem;
tem = len;
int max = 0;
if(i > 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(!key[a[i-1][j] - 'A'])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(!key[a[i+1][j] - 'A'])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(!key[a[i][j-1] - 'A'])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(!key[a[i][j+1] - 'A'])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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;
}