| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
|---|---|---|---|---|---|
| 四色问题 | ★☆☆☆☆ | 答案正确 | 100 | 2014/10/15 0:14:46 | 无 |
地图相邻节点不颜色不同，共有四种颜色，求把所有点染色满的方案数。
还是搜索辣，邻接矩阵转换邻接表，然后四种颜色枚举一遍。
然后有一个问题就是判重，重复的状态容易导致冗余的搜索。我们可以用二进制压位（位运算）解决这个问题。一共四种颜色加上未染色，每个节点共5种状态，所以一个点3bit即可，最多8个点需要的空间大约为1kw左右，差不多是不会爆内存的。
然后就写了个八进制位运算的类。
That's all.
| 1116.cpp代码已折叠
展开折叠内容
|
|---|
#include<cstdio>
#include<vector>
#include<iostream>
class ocx
{
private:
int on;
public:
ocx(int u):
on(u)
{}
void set(const int &index, const int&val)
{
on&=~(7<<(index*3));
on|=(1<<(index*3))*val;
}
void printBin()//二进制逆序输出
{
int u=on;
std::cout<<"0b";
while(u)
{
std::cout<<u%2;
u>>=1;
}
std::cout<<std::endl;
}
const int operator [](const int &index)
{
return 7&(on>>(index*3));
}
operator int()
{
return on;
}
};
int count=0;
std::vector<int> map[10];
int n;
bool g[10000001]={};
void dfs(const int& painted,const int& node,ocx state)
{
for(int i=1;i<=4;++i)
{
bool accepted=1;
for(int j=0;j<map[node].size();++j)
{
if(state[map[node][j]]==i)
{
accepted=0;
break;
}
}
if(accepted)
{
state.set(node,i);
if(g[state])
continue;
g[state]=1;
if(painted == n-1)
{
++count;
continue;
}
for(int j=0;j<n;++j)
{
if(!state[j])
{
dfs(painted+1,j,state);
}
}
}
}
}
int main()
{
std::cin>>n;
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
bool b;
std::cin>>b;
if(b)
{
map[i].push_back(j);
map[j].push_back(i);
}
}
}
dfs(0,0,0);
std::cout<<count;
return 0;
}
|
CloudLunar