加载中…
个人资料
abentu
abentu
  • 博客等级:
  • 博客积分:0
  • 博客访问:15,882
  • 关注人气:4
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

poj2148-Color the Map

(2010-07-19 07:43:00)
标签:

杂谈

    一道计算几何和搜索的综合题,题目的意思是给你一些区域,他们分属于一些国家,这些区域组成了一个地图,现在让你为地图染色,要求颜色尽量少,相同国家必须染相同颜色;不同国家的区域交界是颜色必须不同。也就是说,先用计算几何计算出各个区域之间或者国家之间的邻接关系,然后再找最小颜色数即可。

    有一个小问题,这个题目并非最多4种颜色即可染掉所有区域,因为有些区域是被强制染成同一种颜色,而且这些染成同一种颜色的区域的个数不定,所以不能用四色定理得出结论,还是要老老实实地dfs,答案可能会达到9或者10。

 

注意判断两条线段有重合部分的情况(我仅这个函数就写得很麻烦)。

 

代码:

 

#include "iostream"
#include "string.h"
#include "math.h"
using std::cin;
#define N 110
#define M 11


typedef struct
{
 int x,y;
}point1;

bool link[M][M];
int n,block[N],len[N],pn,color[M];
point1 b[N][N];
char name[M][21],s[21];

bool result;

int dfs(int u,int clr)
{
 int i;
 bool judge[11];
 if (u > pn)
 {
  result = 1;
  return 0;
 }

 for (i = 1;i <= clr;i ++)
  judge[i] = 1;

 for (i = 1;i <= pn;i ++)
 if (link[i][u] != 0 && color[i] != 0)
 {
  judge[color[i]] = 0;
 }

 for (i = 1;i <= clr;i ++)
 if (judge[i] == 1)
 {
  color[u] = i;
  dfs(u+1,clr);
  color[u] = 0;
 }

 return 0;
}

bool fourin(point1 w1,point1 w2,point1 w3,point1 w4)
{
 if ( (w2.x - w1.x) * (w4.y - w3.y) == (w4.x - w3.x) * (w2.y - w1.y) )
 if ( (w3.x - w1.x) * (w4.y - w2.y) == (w4.x - w2.x) * (w3.y - w1.y) )
 if ( (w4.x - w1.x) * (w2.y - w3.y) == (w2.x - w3.x) * (w4.y - w1.y) )
 {
  if ((w1.x < w3.x && w3.x < w2.x) || (w1.x < w4.x && w4.x < w2.x) || (w2.x < w3.x && w3.x < w1.x) || (w2.x < w4.x && w4.x < w1.x) || (w3.x < w1.x && w1.x < w4.x) || (w3.x < w2.x && w2.x < w4.x) || (w4.x < w1.x && w1.x < w3.x) || (w4.x < w2.x && w2.x < w3.x))
  return (1);
  else if ((w1.y < w3.y && w3.y < w2.y) || (w1.y < w4.y && w4.y < w2.y) || (w2.y < w3.y && w3.y < w1.y) || (w2.y < w4.y && w4.y < w1.y) || (w3.y < w1.y && w1.y < w4.y) || (w3.y < w2.y && w2.y < w4.y) || (w4.y < w1.y && w1.y < w3.y) || (w4.y < w2.y && w2.y < w3.y))
   return (1);
  else if ((w1.x == w3.x && w2.x == w4.x && w1.y == w3.y && w2.y == w4.y) || (w1.x == w4.x && w2.x == w3.x && w1.y == w4.y && w2.y == w3.y))
   return (1);
 }
 return (0);
}


int judgelink(int u,int v)
{
 int i,j,leni,lenj,g1,g2,h1,h2;

 if (block[u] == block[v])
  return 0;

 leni = len[u];
 lenj = len[v];

 for (i = 1;i <= leni;i ++)
 for (j = 1;j <= lenj;j ++)
 {
  g1 = i;
  g2 = i+1;
  if (g1 == leni)
   g2 = 1;
  h1 = j;
  h2 = j+1;
  if (h1 == lenj)
   h2 = 1;
 
  if (fourin(b[u][g1],b[u][g2],b[v][h1],b[v][h2]) == 1)
  {
   link[block[u]][block[v]] = 1;
   link[block[v]][block[u]] = 1;
   return 0;
  }
 }

 return 0;
}

 

int init()
{
 memset(link,0,sizeof(link));
 memset(block,0,sizeof(block));
 memset(len,0,sizeof(len));
 memset(name,0,sizeof(name));
 memset(b,0,sizeof(b));

 int i,j,xx,yy;
 bool judge;

 pn = 0;
 for (i = 1;i <=n;i ++)
 {
  scanf("%s",&s);

  judge = 0;
  for (j = 1;j <= pn;j ++)
  {
   if (strcmp(name[j],s) == 0)
   {
    block[i] = j;
    judge = 1;
    break;
   }
  }
  if (judge == 0)
  {
   pn ++;
   strcpy(name[pn],s);
   block[i] = pn;
  }

  len[i] = 0;
  while (scanf("%d",&xx) != EOF && xx != -1)
  {
   scanf("%d",&yy);
   len[i] ++;
   b[i][len[i]].x = xx;
   b[i][len[i]].y = yy;
  }
 }

 return 0;
}


int solve()
{
 int i,j,k;
 for (i = 1;i <= n-1;i ++)
 for (j = i+1;j <= n;j ++)
  judgelink(i,j);
 

 memset(color,0,sizeof(color));
 
 for (k = 1;k <= 10;k ++)
 {
  result = 0;
  dfs(1,k);
  if (result == 1)
  {
   printf("%d\n",k);
   return 0;
  }
 }
 return 0;
}

 

int main()
{
 freopen("3.txt","r",stdin);

 while (scanf("%d",&n) != EOF && n > 0)
 {
  cin.ignore();
  init();
  solve();
 }

 return 0;
}

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有