poj2488-Knight’s Journey(DFS马踏棋盘)

发布于 2019-07-25  1.02k 次阅读


问题传送门:

题意:

给你一个p×q的棋盘(p×q<26),问一匹马不重复的走完所有点的路径是什么
如果有多条路径,输出字典序最小的那个。
如果没有,输出impossible。

分析:

看了很多文章,大家都说:从某一点可以遍历所有点,那么从任意点都可以。
这是一个假命题!
从某一点可以遍历所有点,不代表从任一点都可以遍历。
因为是要求不重复的。
但是,终点来了,如果存在一条路径可以遍历整个棋盘,
那么从(0,0)这个点一定可以遍历整个棋盘!
也就是说,在这一题中,要求输出字典序最小的路径,
不需要把所有的路径找出来,直接从(0,0)开始深搜,如果有,就是答案。
当然,方向数组也需要按照字典序。但是我当时没有考虑这个,也AC了。
应该是数据不严格吧
为什么呢?
我们把棋盘看成黑白相间的,设(0,0)是黑色。
有一个事实,如果这一步是黑,那么下一步一定是白。
也就是,如果从黑开始走,假设可以遍历整个棋盘的情况下,
黑的数量=白,  或者, 黑的数量=白+1
这就是我得出结论的原因所在,如果是上述第二种情况,从白开始走,就不能遍历所有。

代码:

#include <iostream>
#include <string>
using namespace std;

int p, q, f;
int Next[8][2]={{-2,-1},{-1,-2},{-2,1},{-1,2},
				{2,1},{1,2},{2,-1},{1,-2}};
int vis[50][50];

struct Node
{
	int px,py;
}G[50][50];

string path;

void getPath(int x, int y)
{
	Node t ;
	string tp;
	for (int i = 0; i < p*q; i++)
	{
		t = G[x][y];
		tp = (char)(x+1+'0') + tp;
		tp = (char)(y+65) + tp;
		x = t.px, y = t.py;
	}
	path = min(path, tp);
}


void DFS(int x, int y, int cnt)
{
	if (cnt == p*q)
	{
		f = 1;
		getPath(x,y);
		return;
	} 	
	for (int i = 0; i < 8; i++)
	{
		int nx = Next[i][0] + x;
		int ny = Next[i][1] + y;
		if (nx<0||nx>=p||ny<0||ny>=q||vis[nx][ny]) 
			continue;
		vis[nx][ny] = 1;
		G[nx][ny].px = x;
		G[nx][ny].py = y;
		DFS(nx,ny,cnt+1);
		vis[nx][ny] = 0;
	}
}

void clean()
{
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
		{
			vis[i][j] = 0;
			G[i][j].px = 0, G[i][j].py = 0;
		}
}

int main()
{
	int T;
	cin >> T;
	for (int k = 1; k <= T; k++)
	{
		f = 0;
		clean();
		path = "ZZZZ";
		cin >> p >> q;
		vis[0][0] = 1;
		DFS(0,0,1);
		cout << "Scenario #"<<k<<":" << endl;
		if (path[1] == 'Z')
			cout << "impossible" << endl;
		else		
			cout << path << endl;
		cout << endl;
	}
	return 0;
}

Simple And Clear