gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
POJ 2488(简单的深搜)
  1#include <cstdio>
  2#include <memory.h>
  3
  4const int MAXN = 900 ;
  5const int SIZE = 27 ;
  6
  7int P , Q , arr[MAXN][2] , sum ;
  8bool ok , visited[SIZE][SIZE] ;
  9
 10void DFS(const int& x, const int& y, int num )
 11{
 12    if ( ok ) return ;
 13
 14    arr[num][0] = x , arr[num][1] = y ;
 15    if ( num == sum )
 16    {
 17        ok = true ;
 18        return ;
 19    }
 20
 21    if ( y - 2 > 0 )
 22    {
 23        if ( x - 1 > 0 && !visited[x - 1][y - 2] )
 24        {
 25            visited[x - 1][y - 2] = true ;
 26            DFS( x - 1, y - 2, num + 1 ) ;
 27            visited[x - 1][y - 2] = false ;
 28        }
 29        if ( x + 1 <= P && !visited[x + 1][y - 2] )
 30        {
 31            visited[x + 1][y - 2] = true ;
 32            DFS( x + 1, y - 2, num + 1 ) ;
 33            visited[x + 1][y - 2] = false ;
 34        }
 35    }    
 36    if ( x - 2 > 0 )
 37    {
 38        if ( y - 1 > 0 && !visited[x - 2][y - 1] )
 39        {
 40            visited[x - 2][y - 1] = true ;
 41            DFS( x - 2, y - 1, num + 1 ) ;
 42            visited[x - 2][y - 1] = false ;
 43        }
 44    }
 45    if ( x + 2 <= P )
 46    {
 47        if ( y - 1 > 0 && !visited[x + 2][y - 1] )
 48        {
 49            visited[x + 2][y - 1] = true ;
 50            DFS( x + 2, y - 1, num + 1 ) ;
 51            visited[x + 2][y - 1] = false ;
 52        }
 53    }
 54    if ( x - 2 > 0 )
 55    {
 56        if ( y + 1 <= Q && !visited[x - 2][y + 1] )
 57        {
 58            visited[x - 2][y + 1] = true ;
 59            DFS( x - 2, y + 1, num + 1 ) ;
 60            visited[x - 2][y + 1] = false ;
 61        }
 62    }    
 63    if ( x + 2 <= P )
 64    {
 65        if ( y + 1 <= Q && !visited[x + 2][y + 1] )
 66        {
 67            visited[x + 2][y + 1] = true ;
 68            DFS( x + 2, y + 1, num + 1 ) ;
 69            visited[x + 2][y + 1] = false ;
 70        }
 71    }
 72    if ( y + 2 <= Q )
 73    {
 74        if ( x - 1 > 0 && !visited[x - 1][y + 2] )
 75        {
 76            visited[x - 1][y + 2] = true ;
 77            DFS( x - 1, y + 2, num + 1 ) ;
 78            visited[x - 1][y + 2] = false ;
 79        }
 80        if ( x + 1 <= P && !visited[x + 1][y + 2] )
 81        {
 82            visited[x + 1][y + 2] = true ;
 83            DFS( x + 1, y + 2, num + 1 ) ;
 84            visited[x + 1][y + 2] = false ;
 85        }
 86    }    
 87}
 88
 89void Init()
 90{
 91    ok = false ;
 92    memset(visited, 0, sizeof(visited)) ;
 93}
 94int main()
 95{
 96//    freopen("in.txt", "r", stdin) ;
 97
 98    int t , cs ;
 99    
100    cs = 1 ;
101    scanf("%d", &t) ;
102
103    while ( t-- )
104    {
105        Init() ;
106
107        scanf("%d %d", &P, &Q) ;
108
109        sum = P * Q ;
110        
111        visited[1][1] = true ;
112
113        DFS( 1, 1, 1 ) ;
114
115        printf("Scenario #%d:\n", cs) ;
116        cs++ ;
117        
118        if ( ok )
119        {
120            for ( int i = 1 ; i <= sum ; ++i )
121            {
122                printf("%c%c", arr[i][1] + 'A' - 1 , arr[i][0] + '0' ) ;
123            }
124        }
125        else {
126            printf("impossible") ;
127        }
128        printf("\n\n") ;
129    }
130
131    return 0 ;
132}
posted on 2008-11-18 23:26 巫 阅读(391) 评论(0)  编辑 收藏 引用 所属分类: 搜索

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