POJ 2488
1267 ワード
#include
using namespace std;
int visited[30][30];
struct Pos{
int r, c;
};
Pos path[30];
Pos mov[8] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
{1, -2}, {1, 2}, {2, -1}, {2, 1}};
int p, q;
bool DFS(int r, int c, int steps);
int main()
{
int t;
// scanf("%d", &t);
cin >> t;
int i, j, k;
int m;
for(i = 1; i <= t; i++){
printf("Scenario #%d:
", i);
// scanf("%d%d", &p, &q);
cin >> p >> q;
memset(visited, 0, sizeof(visited));
for(j = 0; j < q; j++){
for(k = 0; k < p; k++){
if(DFS(j, k, 0)){
j = q + 10;
for(m = 0; m < p*q; m++){
printf("%c%d", path[m].r + 'A', path[m].c + 1);
}
break;
}
}
}
if(j == q) printf("impossible");
printf("
");
}
return 0;
}
bool DFS(int r, int c, int steps)
{
if(steps == p*q) return true;
if(r < 0 || c < 0 || r >= q || c >= p) return false;
if(visited[r][c]) return false;
int i;
visited[r][c] = 1;
path[steps].r = r;
path[steps].c = c;
for(i = 0; i < 8; i++){
if(DFS(r + mov[i].r, c + mov[i].c, steps + 1)) return true;
}
visited[r][c] = 0;
return false;
}