浙江财经大学
信息管理与工程学院

POJ 2488 A Knight’s Journey

本文由 Ocrosoft 于 2016-10-31 17:10:08 发表
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

题意:一个马在棋盘的0,0位置(注意这个棋盘的方向,跟平时的坐标系不同),问这马能不能不重复地走遍这个棋盘。如果能,按照字典序输出路径。
思路:按照字典序,就是dir数组按照字典序排列,路径记录开俩数组就行了。

#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;
}

欢迎分享与转载,请保留链接与出处。Ocrosoft » POJ 2488 A Knight’s Journey

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址