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

const int maxn = 50;

int b[8]={-2-2-1-11122},a[8]={-11-22-22-11};
bool check[maxn][maxn], flag;
int ansx[maxn], ansy[maxn];
int row, col;

void dfs(int x, int y, int sum)
{
    
if(sum == col * row)
    {
        
for(int i=1; i<=sum; i++)
        printf(
"%c%d", ansy[i]+'A'-1, ansx[i]);
        printf(
"\n");
        flag
=1;
        
return;
    }
    
for(int i=0; i<8 && !flag; i++)
    {
        
if(!flag && !check[x+a[i]][y+b[i]] && x+a[i]>0 && x+a[i]<=row && y+b[i]>0 && y+b[i]<=col)
        {
            ansx[sum
+1= x+a[i];
            ansy[sum
+1= y+b[i];
            check[x
+a[i]][y+b[i]] = 1;
            dfs(x
+a[i], y+b[i], sum+1);
            check[x
+a[i]][y+b[i]] = 0;
        }
    }
}

int main()
{
    
int n;
    
int cas;
    
while(~scanf("%d",&n))
    {
        cas
=1;
        
while(n--)
        {
            flag 
= 0;
            memset(check,
0,sizeof(check));
            printf(
"Scenario #%d:\n",cas++);
            scanf(
"%d%d"&row, &col);
            check[
1][1]=1;
            ansx[
1= ansy[1= 1;
            dfs(
111);
            
if(!flag) printf("impossible\n");
            printf(
"\n");
        }
    }
    
return 0;
}
posted on 2010-07-29 07:18 Vontroy 阅读(141) 评论(0)  编辑 收藏 引用 所属分类: 搜索POJ

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