hdu 2821(dfs)

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=2821
考え方:最初は気づかなかったので、map[i][j]=0の位置から始めなければなりません.そしてdfsです.遡及するときは少し注意すればいいです.

 1 #include<iostream>

 2 #include<cstdio>

 3 #include<cstring>

 4 #include<algorithm>

 5 #include<string>

 6 using namespace std;

 7 

 8 int n,m,cnt;

 9 char str[33];

10 int map[33][33];

11 int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

12 char Dir[7]={'U','D','L','R'};

13 char path[1111];

14 

15 bool Judge(int x,int y)

16 {

17     if(x>=0&&x<n&&y>=0&&y<m)

18         return true;

19     return false;

20 }

21 

22 bool dfs(int x,int y,int len)

23 {

24     if(len>=cnt){

25         path[len]=0;

26         return true;

27     }

28     for(int i=0;i<4;i++){

29         int xx=x+dir[i][0];

30         int yy=y+dir[i][1];

31         if(!Judge(xx,yy)||map[xx][yy])continue;

32         while(Judge(xx,yy)&&!map[xx][yy]){

33             xx+=dir[i][0];

34             yy+=dir[i][1];

35         }

36         if(!Judge(xx+dir[i][0],yy+dir[i][1]))continue;

37         int tmp=map[xx][yy];

38         map[xx+dir[i][0]][yy+dir[i][1]]+=tmp-1;

39         map[xx][yy]=0;

40         path[len]=Dir[i];

41         if(dfs(xx,yy,len+1))return true;

42         map[xx+dir[i][0]][yy+dir[i][1]]-=tmp-1;

43         map[xx][yy]=tmp;

44     }

45     return false;

46 }

47 

48 

49 

50 int main()

51 {

52     while(~scanf("%d%d",&m,&n)){

53         cnt=0;

54         for(int i=0;i<n;i++){

55             scanf("%s",str);

56             for(int j=0;j<m;j++){

57                 if(str[j]!='.'){

58                     cnt+=str[j]-'a'+1;

59                     map[i][j]=str[j]-'a'+1;

60                 }else 

61                     map[i][j]=0;

62             }

63         }

64         bool flag=false;

65         for(int i=0;i<n;i++){

66             for(int j=0;j<m;j++){

67                 if(map[i][j]==0&&dfs(i,j,0)){ //   map[i][j]==0     

68                     flag=true;

69                     printf("%d
%d
",i,j);

70                     cout<<path<<endl;

71                     break;

72                 }

73             }

74             if(flag)break;

75         }

76     }

77     return 0;

78 }

View Code