POJ 1154 LETTERS

典型的深度优先搜索策略的回溯题。。

因为一直WA。。所以写一下总结。。帮助自己回忆一下。。

深搜的概念和回溯的方法，百度上很多，我就不多说什么了。

为什么一直WA？当然和题目数据无关，是我自己的问题。。

第一，判断是否在地图内。边界错了，我都不知道是怎么写出来的，边界判断错了。真心无语。。

第二，这道题和迷宫问题最大的不同时它不会回溯已经走过的点。

第三，回溯中用来判断回溯条件的栈，同样是以0 为起点的。。（用数组实现）

第四，我的算法功底不好，这也是我最想说的，最基本的尤为重要。不是第一道回溯题，却是最痛苦的一道。

AC的时候，心里有一种难以言喻的喜悦，但并不开心，一道简单的题嘛。。。

思路就是搜索当前的节点的字母是否出现过，如果出现过，则不扩展这个节点，否则扩展这个节点。扩展策略为深度优先。。

贴代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

char letter[100][100];
int jud[100][100];
char dd[100];

int cnt;
int cnt1;
int number;
int direct[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int R,C;

bool inmap(int row,int col)
{
    if(row>=0&&col>=0&&row<R&&col<C)
      return true;
    else 
      return false;
}

bool traceback(int row,int col)
{ int i,j;
  int row1,col1; 
  bool flag;
  
  dd[number]=letter[row][col];
  jud[row][col]=1;
  cnt++;
  number++;
  
  if(cnt>cnt1) cnt1=cnt;
  
  for(i=0;i<4;i++)
  {  row1=row+direct[i][0];
     col1=col+direct[i][1];
     
     if(inmap(row1,col1))
       {   
       
             flag=true;
             for(j=0;j<number;j++)
              {
                  if(dd[j]==letter[row1][col1])
                     {flag=false;
                       break;}
              }
              if(flag==false)
                continue;
                else
              traceback(row1,col1);
       } 

  }
  
  cnt--;
  number--;
 return false;
}

int main()
{
 int i,j;
 scanf("%d%d",&R,&C);
 getchar();
 
 for(i=0;i<R;i++)
 { for(j=0;j<C;j++)
  scanf("%c",&letter[i][j]);
   getchar();
 }
 
  number=0;
  memset(dd,0,sizeof(dd));
  memset(jud,0,sizeof(jud));
  cnt=0;
  cnt1=0;
  traceback(0,0);    
    
  printf("%d\n",cnt1);    
    
return 0;
}

另外一组测试数据：

5 5

ABAAA

BCAAA

CDERT

SDFGH

LLLLL

正确是：12