给矩阵每个部分上不同颜色 C语言

来源：百度知道 编辑：UC知道 时间：2024/05/29 00:47:26
一道奥赛上的习题..

设一图形有n个区域(1<=n<=100),各区域的相临关系用0(不相临).1(相临)表示.

将图的每一部分涂上红(1),黄(2),蓝(3),绿(4)等4种颜色致意.要求各相临部分的颜色不同.

输入 : n
n*n的01矩阵

输出 : 每个区域的颜色码

-----
我想用递归来做 4种颜色依次去试 ..遇到相临部分有这种颜色便用下一种颜色.如果4种颜色都试完了,就回归到n-1的部分.更改n-1部分的颜色.

//dfs 回溯实现 100个顶点时间复杂度太大
#include <iostream>
using namespace std;

const int M=20;//图的最大顶点数目
int n,count=0;//图的实际定点数目以及着色总数
int map[M][M]={0};//图的邻接矩阵
int color[M]={0};//存储每个顶点颜色

void print()//打印着色方案
{
count++;
cout<<"方案"<<count<<':';
int i;
for(i=1;i<=n;i++)
cout<<color[i]<<' ';
cout<<endl;
}

bool ok(int dep,int i)//判断顶点dep是否可用i着色
{
int j=1;
for(;j<=n;j++)
if(map[dep][j]&&color[j]==i)
return false;
return true;
}

void find(int dep)//给第dep个顶点着色
{
int i;
for(i=1;i<=4;i++)
if(ok(dep,i))
{
color[dep]=i;
if(dep==n) print();
else find(dep+1);
color[dep]=0;
}
}

int main()
{
freopen("input.txt","r",stdin);
cout<<"请输入图的顶点数目：&quo