【wikioi】1116 四色問題

題目連結

算法：DFS

剛開始卡了一下，但後面想了想，于是

放上代碼：

#include <iostream>

using namespace std;
bool map[9][9];
int c[9]; //随便命名四種顔色
int ans = 0, N;
//依次枚舉每個節點，來試與前面的節點是否有重合的，沒有就下一層
void dfs(int n)
{
	int i, j;
	if(n > N) {ans++; return;}
	for(j = 1; j <= 4; j++) //依次枚舉4種顔色
	{
		for(i = 1; i < n; i++) if(map[i][n] && c[i] == j) break; //判斷與n是否有連結并且顔色有無重合
		if(i == n) //沒有重合，拓展下一節點
		{
			c[n] = j;
			dfs(n+1);
			c[n] = 0;
		}
	}
}
int main()
{
	cin >> N;
	int i, j;
	for(i = 1; i <= N; i++) for(j = 1; j <= N; j++) cin >> map[i][j];
	dfs(1);
	cout << ans;
	return 0;
}