[wikioi]四色问题

http://wikioi.com/problem/1116/

典型的DFS。

#include <iostream>
#include <memory.h>

#define LEN 8
using namespace std;

int graph[LEN][LEN];
int color[LEN]; // 1,2,3,4 for 4 colors
int ans = 0;
int n = 0;

void dfs(int step) {
    if (step == n) {
        ans++;
        return;
    }
    for (int x = 1; x <= 4; x++) {
        bool valid = true;
        for (int i = 0; i < step; i++) {
            if (graph[i][step] == 1 && color[i] == x) {
                valid = false;
                break;
            }
        }
        if (valid) {
            color[step] = x;
            dfs(step+1);
            color[step] = 0;
        }
    }
}
 
int main()
{
    memset(graph, 0, sizeof(graph));
    memset(color, 0, sizeof(color));
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }
    dfs(0);
    cout << ans << endl;
    return 0;
}