UVa 539 The Settlers of Catan

題目連結
想法：
　　將每個點能連到哪些點存起來，然後對每個點使用DFS看該點最遠能走多深。

	#include <cstdio>
	#include <vector>
	using namespace std;
	int DFS (int node, vector<int> toNode[30], int dis, bool visit[][30])
	{
	int longest_length = 0; // 當前node能走的最遠距離
	for (int nxt_node : toNode[node]){
	if (!visit[node][nxt_node]) { // 該條線還沒走過
	visit[node][nxt_node] = 1;
	visit[nxt_node][node] = 1; // 雙向關閉
	int length = DFS (nxt_node, toNode, dis+1, visit);
	if (length > longest_length) longest_length = length;
	visit[node][nxt_node] = 0;
	visit[nxt_node][node] = 0; // 雙向開啟
	}
	}
	if (longest_length == 0) return dis; //如果走到底 回傳當前距離
	else return longest_length; //否則回傳該點能走的最長距離
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int n, m;
	while (scanf("%d%d", &n, &m)) {
	if (!n && !m) break;
	vector<int> toNode[30]; // toNode[i]儲存i_node能走向哪幾個點
	for (int i=0, n1, n2; i<m; ++i) {
	scanf("%d%d", &n1, &n2);
	toNode[n1].push_back(n2);
	toNode[n2].push_back(n1);
	}
	bool visit[30][30] = {0}; //visit[i][j]=1 表示i_j這條線已經走過
	int longest = 0;
	for (int i=0; i<n; ++i){
	int length = DFS(i, toNode, 0, visit);
	if (length > longest)
	longest = length;
	}
	printf("%d\n", longest);
	}
	}

view raw [UAa] 539 The Settlers of Catan.cpp hosted with ❤ by GitHub