(step4.3.8)hdu 2181(哈密顿绕行世界问题—

题目大意:通俗点讲就是，输出所有从m城市出发,便利所有城市之后又能回到m城市的序列......

解题思路:DFS

1）用map[][]来存储城市之间的连通情况.用used[]存储某个城市的使用情况(即某一个城市是否被访问过).用res[]保存路径

。如res[count] = dep ; 表示的是第count不访问的城市是dep。用cas表示目标城市的序号

代码如下:

/*

 * 2181_2.cpp

 *

 *  Created on: 2013年8月22日

 *      Author: Administrator

 */

#include <iostream>

using namespace std;

/**

 * map[][] :用来保存城市之间的连通情况

 * used[] :用来 保存城市的使用情况

 * res[] :用来保存路径

 * cas :目标城市的标号

 */

const int maxn = 21;

bool map[maxn][maxn];

bool used[maxn];

int res[maxn];

int cas;

int num = 1;

/**

 * dep :当前访问城市

 * count :当前访问的城市数

 */

void dfs(int dep, int count) {

	int i;

	//第count个所到达的城市是dep

	res[count] = dep;

	if (count == 19) { //19步能涉及20个城市

		if (map[dep][cas]) {

			printf("%d: ", num++);

			for (i = 0; i < 20; ++i) {

				printf(" %d", res[i]);

			}

			printf(" %d", cas);

			printf("\n");

		}

		return;

	}

	for (i = 1; i <= 20; ++i) {

		/**

		 * map[dep][j] :从城市dep到城市j的连通情况

		 */

		//如果城市dep与城市j连通&&城市j没有使用过

		if (map[dep][i] && !used[i]) {

			used[i] = true;

			dfs(i, count + 1);

			used[i] = false;

		}

	}

}

int main() {

	memset(map, 0, sizeof(map));

	memset(res, 0, sizeof(res));

	memset(used, false, sizeof(used));

	int i;

	int a, b, c;

	for (i = 1; i <= 20; ++i) {

		scanf("%d%d%d", &a, &b, &c);

		map[i][a] = true;

		map[i][b] = true;

		map[i][c] = true;

	}

	while (scanf("%d", &cas) != EOF, cas) {

		used[cas] = true;

		dfs(cas, 0);

	}

}

巴特西

(step4.3.8)hdu 2181(哈密顿绕行世界问题——DFS)

最新文章

热门文章