大早晨的~呵呵,附上1154

       昨天在寝室写的1154还是比较简单的DFS,开始的时候忘记了路径的复原,还有就识要注意一下,最开始的点要标记。
      代码:

#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;
}

 

posted on 2009-03-06 08:43 成大才子 阅读(166) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年3月>
22232425262728
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

公告

关于更多关于成大才子,请访问http://hi.baidu.com/成大才子

常用链接

留言簿(1)

随笔档案

文章分类

文章档案

链接

搜索

最新评论

阅读排行榜

评论排行榜