#include <stdio.h>
#include <string.h>
const int maxn = 50;
int b[8]={-2, -2, -1, -1, 1, 1, 2, 2},a[8]={-1, 1, -2, 2, -2, 2, -1, 1};
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(1, 1, 1);
if(!flag) printf("impossible\n");
printf("\n");
}
}
return 0;
}
posted on 2010-07-29 07:18
Vontroy 閱讀(171)
評論(0) 編輯 收藏 引用 所屬分類:
搜索 、
POJ