poj 2488

题意：骑士周游问题，按照给你的走法,问骑士能否在p * q的棋盘上，从某个点出发不重复走遍棋盘每个点，如果能，输出骑士每步的位置（按字典序），如果不能，则输出impossible。

思路：很好的dfs，变1维为2维，但思路是差不多的，走法可能有多种，必须严格按照字典序走。   题目要求以"lexicographically"方式输出，也就是字典序...要以字典序输出路径，那么搜索的方向（我的程序记录位置的数组是path[]),以特殊的顺序排列了...这样只要每次从dfs(A,1)开始搜索，第一个成功遍历的路径一定是以字典序排列.注意回溯输出

代码如下：

#include<iostream>
using namespace std;
const int Max = 25;



bool visit[Max][Max], output;
int visit_num, p, q;      // visit_num记录要走的点数。
char path[2 * Max];       // path[]记录路径。
int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};   // 字典序。



void dfs(int depth, int x, int y)
{
    if(depth == visit_num)
	{
        for(int i = 0; i < 2 * depth; i ++)
            cout << path[i];
        cout << endl << endl;
        output = true;
        return;
    }
    for(int i = 0; i < 8 && output == false; i ++)
	{
		int new_x = x + dx[i];
		int new_y = y + dy[i];
		if(new_x > 0 && new_y > 0 && new_x <= q && new_y <= p && visit[new_y][new_x] == false)
		{
			visit[new_y][new_x] = true;
			
			path[2 * depth ] = 'A' + new_x - 1;
			path[2 * depth + 1] = '1' + new_y - 1;
			dfs(depth + 1, new_x, new_y);
			visit[new_y][new_x] = false;
			
        }
    }
	
}



int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
	{
        cin >> p >> q;
        cout << "Scenario #" << i << ':' << endl;
		
		
		
        for(int y = 1; y <= p; y ++)
            for(int x = 1; x <= q; x ++)
                visit[y][x] = false;
			visit_num = p * q;
			output = false;   
			visit[1][1] = true;
			path[0] = 'A';
			path[1] = '1';   // 初始化，设A1为首位置（证明如果能走完的话，必存在一条起点为A1的路径）
			dfs(1,1,1);
			
			
			
			if(output == false)
				cout << "impossible" << endl << endl;
    }
    return 0;
}

 

 关于DFS的问题未完待续……