﻿POJ 2488 A Knight's Journey-Ocrosoft

# POJ 2488 A Knight's Journey

A Knight’s Journey

Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu

Description

Background
The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey
around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?
Problem
Find a path such that the knight visits every square once. The knight can start and end on any square of the board.

Input

The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .

Output

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.
If no such path exist, you should output impossible on a single line.

Sample Input

```3
1 1
2 3
4 3```

Sample Output

```Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4```

Sample Input

```3
1 1
2 3
4 3```

Solution

```#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 26 + 10;
const int MOD = 1000000009;
int gcd(int a, int b)
{
if (!b)return a;
return gcd(b, a%b);
}
using namespace std;
//or2..or2..or2..or2..//
int n, m, cas = 0;
int ax[MAXN], ay[MAXN];//路径记录
bool vis[MAXN][MAXN], flag;
int dir[8][2] = { { -2,-1 },{ -2,1 },{ -1,-2 },{ -1,2 },{ 1,-2 },{ 1,2 },{ 2,-1 },{ 2,1 } };
void dfs(int px,int py, int cnt)
{
if (flag)return;
ax[cnt] = px, ay[cnt] = py;
if (cnt == n*m) { flag = true; return; }

for (int i = 0; i < 8; i++)
{
int x = px, y = py;
x += dir[i][0], y += dir[i][1];
if (x <= 0 || x > n || y <= 0 || y > m)continue;
if (vis[x][y])continue;
if (flag)return;
vis[x][y] = true;
dfs(x, y, cnt + 1);
vis[x][y] = false;
}
}
int main()
{
int N; cin >> N;
while (N--)
{
cin >> m >> n;
ms(vis); flag = false; vis[1][1] = true;
printf("Scenario #%d:\n", ++cas);

dfs(1, 1, 1);
if (flag)
{
for (int i = 1; i <= n*m; i++)
printf("%c%d", ax[i] + 'A' - 1, ay[i]);
}
else
printf("impossible");
printf("%s", N ? "\n\n" : "\n");
}
return 0;
}```