OpenJudge NOI 2.5 1490:A Knight‘s Journey

【題目連結】

OpenJudge NOI 2.5 1490:A Knight’s Journey

疑問：題目說可以從任意點出發，以任意點結束。為什麼我看他人的代碼中，隻寫從(1，1）出發的情況也能過呢？哪位朋友如能了解，希望不吝賜教。

【題目翻譯】

一個騎士的旅程

描述

背景：

騎士已經厭倦了一次又一次地看黑白方格，而後決定環遊世界。

無論什麼時候，一個騎士都會在一個方向移動兩格，在與其垂直的方向移動一格。

一個騎士的世界就是它所在的棋盤。我們的騎士生活在一個面積小于8*8的棋盤上，但棋盤仍是個長方形。你能幫助這個有冒險精神的騎士做旅行計劃嗎？

問題：

找到一條騎士可以對每個格子通路一次的路徑。騎士的起點和終點可以是棋盤上的任何格子。

輸入：

輸入的第一行是一個正整數n。接下來的多行中包含n組測試樣例。每個測試樣例包含一行兩個正整數p和q（1 <= p*q <= 26），代表了一個p*q的棋盤，其中p表示存在多少個不同的方格編号（1,2,…,p），q表示有多少個不同的方格字母，這些字母是拉丁字母表A,B…的前q個字母。

輸出：

每種情況的輸出以一行"Scenario #i:“起始，其中i是從1開始的情況編号。

然後輸出一行，為通過騎士移動通路棋盤上所有方格的路徑，隻輸出字典序排第一的路徑字元串。路徑字元串應該是單獨輸出一行的連接配接了所有通路過的方格名字的字元串。每個方格名字是一個大寫字母後面接一個數字。

如果不存在這樣的路徑，你應該輸出一行"impossible”。

樣例輸入

3

1 1

2 3

4 3

樣例輸出

Scenario #1:

A1

Scenario #2:

impossible

Scenario #3:

A1B3C1A2B4C2A3B1C3A4B2C4

來源

TUD Programming Contest 2005, Darmstadt, Germany

【題目考點】

1. 深搜回溯

【解題思路】

國際象棋的棋盤，數字表示行，字母表示列，因而輸入p，q指的是該棋盤為p行q列。

要輸出的是字典序排第一的路徑字元串，因而搜尋的起始位置應該按字典序從前向後依次嘗試。

起始位置按字典序排列為：A1, A2, …, A8, B1, B2, …，是先看第A列，再看第B列，直到第H列。對于每列，先看第1行，再看第2行。。。

從(x,y)位置出發，可以到達的位置記為(x+a, y+b)，其中(a, b)為行與列的偏移量。

根據字典序的要求，先按列從小到大排列，列相同時按行從小到大排列。從(x, y)位置出發可以到達的位置(x+a, y+b)的周遊順序為（隻寫出偏移量{a, b}）為：{-1, -2}, {1, -2}, {-2, -1}, {2, -1}, {-2, 1}, {2, 1}, {-1, 2}, {1, 2}。

按照該順序周遊從(x, y)可以到達的所有位置，進行搜尋，搜尋從該點出發的所有可能路徑。每到達一個新的位置，将該位置儲存在路徑中（路徑用一個vector儲存）。搜尋結束後，要回溯到前一個位置，繼續搜尋其他可以到達但未到達的位置。

搜尋的過程中做通路格子數量的計數，如果通路數量達到了p*q，則騎士完成了周遊棋盤上的每個格子，輸出路徑。

【題解代碼】

解法1：深搜回溯

#include<bits/stdc++.h>
using namespace std;
#define N 30
struct Pair
{
	int x, y;//x:行 y:列 
	Pair(){}
	Pair(int a, int b):x(a), y(b){}
};
vector<Pair> path;//儲存路徑 每個元素
int dir[8][2] = {{-1, -2}, {1, -2}, {-2, -1}, {2, -1}, {-2, 1}, {2, 1}, {-1, 2}, {1, 2}};
bool vis[N][N], hasAns;//vis[i][j]:(i,j)是否通路過  hasAns：是否已經找到答案 
int p, q;//地圖p行q列 
void dfs(int sx, int sy)
{
	for(int i = 0; i < 8; ++i)
	{
		int x = sx+dir[i][0], y = sy+dir[i][1];
		if(x >= 1 && x <= p && y >= 1 && y <= q && vis[x][y] == false)
		{
			vis[x][y] = true;
			path.push_back(Pair(x, y));
			if(path.size() == p*q)//如果路徑中已經儲存了地圖中的所有位置，即已經通路了所有位置，則找到路徑 
			{
				hasAns = true;
				return;
			}
			dfs(x, y);
			if(hasAns)
				return;
			vis[x][y] = false;
			path.pop_back();
			
		}
	}
}
int main()
{
	int n;
	cin >> n;
	for(int k = 1; k <= n; ++k)//k：情況編号 
	{
		cin >> p >> q;
		memset(vis, 0, sizeof(vis));
		path.clear();
		hasAns = false; 
		for(int j = 1; j <= q; ++j)//先周遊列，再周遊行 
		{
			for(int i = 1; i <= p; ++i)
			{
				if(vis[i][j] == false)
				{
					vis[i][j] = true;
					path.push_back(Pair(i, j));
					if(path.size() == p*q)
						hasAns = true;
					dfs(i, j);
					if(hasAns)
						break;
					vis[i][j] = false;
					path.pop_back();
				}
			}
			if(hasAns)
				break;
		}
		cout << "Scenario #" << k << ":" << endl;
		if(hasAns)
		{
			for(Pair pr : path)
				cout << char(pr.y-1+'A') << pr.x;
		}
		else
			cout << "impossible";
		cout << endl << endl;
	}
	return 0;
}