c++，怎么解决地图着色问题？

地图着色可以使用回溯的方法进行解决。

我们提供的服务有：网站设计、成都网站建设、微信公众号开发、网站优化、网站认证、佳木斯ssl等。为上千家企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务，是有科学管理、有技术的佳木斯网站制作公司

递归描述如下：

在前面n-1个节点都合法的着色之后，开始对第n个节点进行着色。

这时候枚举可用的m个颜色，通过和与它相邻的节点的颜色，来判断这个颜色是否合法。

如果找到那么一种颜色使得第n个节点能够着色，那么说明m种颜色的方案是可行的。

//用于判断当前节点上涂上这个颜色可不可行，与其邻接节点的颜色做判断，这里用邻接表来存储图的信息

bool isOk(int step)

{

vectorint::iterator iter;

for(iter = input[step].begin(); iter != input[step].end(); iter++)

{

if(Color[step] == Color[*iter]) return false;

}

return true;

}

//step表示0-n的节点，color_num是指给color_num的颜色的个数可用

//判断如果给color_num的颜色的个数是否可行，如果可行返回true,否则false 

bool DFS(int step, int color_num)

{

if(step = n) return true;

else

{

int i;

for(i = 1; i= color_num; i++)

{

Color[step] = i;

if(isok(step))

{

if(DFS(step + 1, color_num))

return true;

}

Color[step] = 0;

}

}

return false;

}

求一个java写的地图程序

用java写一个地图编辑器

记得媒体在采访c++之父的时候,他说作为程序员,要相信自己能够解决已经理解的任何事情.

换句话说:您可以解决任何问题,只要想得明白

现实问题:开发一个基于地砖的二维游戏的地图编辑器,要求生成两个binary文件,各包含一个二维数组,*.map存放地砖,花花草草什么的.*.item放道具,比如某个点可能会触发一个事件.很简单,随便写.看到这里您已经大致明白程序的整体结构.

计算机语言:java.

要理解事件必须分析

初步来看,地图编辑器:生成某种形式的若干数组,无论是哪种形式的数组,你的目的:

生成数组.地图是实际是一个(x,y)的二维坐标系,这很容易让人联系到:亦无论

我准备把设置两个程序界面(主界面/map界面),java的布局管理器不好摆弄,不如分开两个class,主界面用jbuilder自动创建的application模块(带菜单).map界面自己写,也是jframe,类之间相互传递消息,map界面将在程序开始时被初始化,也可以在程序从主界面中初始化(有问题)

构建程序

以下内容为程序代码:

basepanel.setlayout(new gridlayout(5, 5));

for (byte i = 0; i 9; i++) {

basemapbutton[i] = new

((icon) pic.getimageicon(i, 0));

basemapbutton[i].setbuttontitle(i);

basemapbutton[i].addactionlistener(buttonlistener);

basepanel.add(basemapbutton[i]);

}

itempanel.setlayout(new gridlayout(5, 5));

for (byte i = 0; i 3; i++) {

itemmapbutton[i] = new mapbutton((icon) pic.getimageicon(i, 1));

itemmapbutton[i].setbuttontitle(i);

itemmapbutton[i].addactionlistener(buttonlistener1);

itempanel.add(itemmapbutton[i]);

}

tabbedpane.addtab("bases", basepanel);

tabbedpane.addtab("items", itempanel);

contentpane.add(tabbedpane, borderlayout.center);

有两个地方要解释:

mapbutton:自己写的一个类

以下内容为程序代码:

import javax.swing.icon;

import javax.swing.jbutton;

public class mapbutton extends jbutton {

public mapbutton() {

super();

}

public mapbutton(string arg0) {

super(arg0);

}

public mapbutton(action arg0) {

super(arg0);

}

public mapbutton(icon arg0) {

super(arg0);

}

public mapbutton(string arg0, icon arg1) {

super(arg0, arg1);

}

public byte width, height;

//public pic_w, pic_y;

public void setbuttontitle(byte w, byte h) {

width = w;

height = h;

}

public void setbuttontitle(byte w){

width =w;

}

public byte getbuttonwidth() {

return width;

}

public byte getbuttonheight() {

return height;

}

}

pic:自己写的mappic类的intance:

以下内容为程序代码:

package com.nenghe.mapeditor;

import javax.swing.imageicon;

public class mappic {

imageicon[] baseimages;

imageicon[] itemimages;

imageicon image1;

public mappic() {

init();

}

public void init() {

baseimages = new imageicon[9];

baseimages[0] = new imageicon(mappic.class.getresource("m1.png"/images/wink.gif[/img]);

baseimages[1] = new imageicon(mappic.class.getresource("m2.png"/images/wink.gif[/img]);

baseimages[2] = new imageicon(mappic.class.getresource("m3.png"/images/wink.gif[/img]);

baseimages[3] = new imageicon(mappic.class.getresource("m4.png"/images/wink.gif[/img]);

baseimages[4] = new imageicon(mappic.class.getresource("m5.png"/images/wink.gif[/img]);

baseimages[5] = new imageicon(mappic.class.getresource("m6.png"/images/wink.gif[/img]);

baseimages[6] = new imageicon(mappic.class.getresource("m7.png"/images/wink.gif[/img]);

baseimages[7] = new imageicon(mappic.class.getresource("m8.png"/images/wink.gif[/img]);

baseimages[8] = new imageicon(mappic.class.getresource("m9.png"/images/wink.gif[/img]);

itemimages = new imageicon[3];

itemimages[0] = new imageicon(mappic.class.getresource("error.png"/images/wink.gif[/img]);

itemimages[1] = new imageicon(mappic.class.getresource("i1.png"/images/wink.gif[/img]);

itemimages[2] = new imageicon(mappic.class.getresource("i2.png"/images/wink.gif[/img]);

}

public imageicon getimageicon(int x, int flags) {

if (flags == 0) {

return baseimages[x];

} else if (flags == 1) {

return itemimages[x];

}

return null;

}

}

写mapbutton在于处理事件的时候可以准确的获得按钮的坐标,忘了说了,map界面中我是用按钮代替地图方格的.这是很容易想到的,最笨也是最省力的办法

pic单独写好改,什么时候内容改变了,很容易改,硬要合写没有也随便.

下面就是事件了

有两个事件要处理,第一个是按钮事件,第二个菜单事件

按钮事件我套用这样的结构

以下内容为程序代码:

actionlistener buttonlistener = new actionlistener() {

public void actionperformed(actionevent e) {

//system.out.println(e.tostring());

mapbutton pressedbutton = (mapbutton) e.getsource();

mapdraw.temp_x = pressedbutton.getbuttonwidth();

mapdraw.temp_y = 0;

//system.out.println(mapdraw.temp_x+" "+mapdraw.temp_y);

}

};

....

basemapbutton[i].addactionlistener(buttonlistener);

jbuilder中把按钮事件事件单独生成一个类,我不明白,看不懂.真的很高深.

菜单事件模型jbuilder自己加的.overwrite

以下内容为程序代码:

public void *_actionperformed(actionevent e) {...}

用两个中间值从主界面向map界面传递按了什么:

这里是map界面中的按钮的事件处理程序

以下内容为程序代码:

actionlistener buttonlistener = new actionlistener() {

public void actionperformed(actionevent e) {

mapbutton pressedbutton = (mapbutton) e.getsource();

pressedwidth = pressedbutton.getbuttonwidth();

pressedheight = pressedbutton.getbuttonheight();

if (temp_y == 0) {

if (item[pressedwidth][pressedheight] != 0) {

item[pressedwidth][pressedheight] = 0;

jfm.showmessage("这里的道具已被置空!\nthe item has been null!"/images/wink.gif[/img];

}

map[pressedwidth][pressedheight] = temp_x;

pressedbutton.seticon((icon) pic.getimageicon(temp_x,

temp_y));

} else {

if (map[pressedwidth][pressedheight] == 0) {

jfm.showmessage("道具不能放在这!\nnot put item at this point!"/images/wink.gif[/img];

} else {

if (temp_x == 0) {

byte value = map[pressedwidth][pressedheight];

item[pressedwidth][pressedheight] = 0;

pressedbutton.seticon((icon) pic.getimageicon(

value, 0));

} else {

pressedbutton.seticon((icon) pic.getimageicon(

temp_x, temp_y));

item[pressedwidth][pressedheight] = temp_x;

}

}

}

}

};

请问两个中间值是什么呢?一目了然哦

最后是生成map

以下内容为程序代码:

public void createmap() throws ioexception {

try {

dataoutputstream mapbinaryfile = new dataoutputstream(

new fileoutputstream(mapeditor.filename + "map"/images/wink.gif[/img]);

dataoutputstream itembinaryfile = new dataoutputstream(

new fileoutputstream(mapeditor.filename + "item"/images/wink.gif[/img]);

mapbinaryfile.writebyte(width);

mapbinaryfile.writebyte(height);

for (byte i = 0; i height; i++)

for (byte j = 0; j width; j++) {

//system.out.println(i+" "+j);

byte mapvalue = map[i][j];

byte itemvalue = item[i][j];

if (mapvalue != 0) {

system.out.println(i+" "+j+" "+ mapvalue);

mapbinaryfile.writebyte(j);

mapbinaryfile.writebyte(i);

mapbinaryfile.writebyte(mapvalue);

}

if (itemvalue != 0) {

itembinaryfile.writebyte(j);//x

itembinaryfile.writebyte(i);//y

itembinaryfile.writebyte(itemvalue);

}

}

mapbinaryfile.close();

itembinaryfile.close();

} catch (eofexception e) {

system.err.println("error"/images/wink.gif[/img];

}

}

地图着色问题C/C++

从一个省开始，给它涂上任意一种颜色1，遍历它旁边的省份，涂上与已经涂色并于他相邻的省份不同的颜色就行了。

理论上4种颜色就够了.地图的四色问题嘛!

可能会有多组解。用递归（dfs)就可以输出所有解了。

地图着色算法C语言源代码

前面我写了一个地图着色（即四色原理）的C源代码。

写完以后想了一下，感觉还不完善，因为从实际操作的角度来考虑，四种可用的颜色放在旁边，不同的人可能会有不同的选择顺序，另外，不同的人可能会选择不同的城市作为着色的起点，而当时的程序没有考虑这个问题。于是，把程序修改为下面的样子，还请同行分析并指出代码中的不足之处：

＃i nclude stdio.h

#define N 21

int allcolor[4];/*可用的颜色*/

int ok(int metro[N][N],int r_color[N],int current)

{/*ok函数和下面的go函数和原来的一样,保留用来比较两种算法*/

int j;

for(j=1;jcurrent;j++)

if(metro[current][j]==1r_color[j]==r_color[current])

return 0;

return 1;

}

void go(int metro[N][N],int r_color[N],int sum,int current)

{

int i;

if(current=sum)

for(i=1;i=4;i++)

{

r_color[current]=i;

if(ok(metro,r_color,current))

{

go(metro,r_color,sum,current+1);

return;

}

}

}

void color(int metro[N][N],int r_color[N],int sum,int start)

{

int i,j,k;

r_color=allcolor[0];

for(i=start+1;i!=start;i=(i+1)%(sum+1))/*把所有编号看作一个环*/

if(i==0)/*城市号从1开始编号,故跳过0编号*/

continue;

else

for(j=0;j4;j++)

{

r_color[i]=allcolor[j];/*选取下一种颜色,根据allcolor中颜色顺序不同，结果不同*/

for(k=1;ki;k++)/*检查是否有冲突，感觉还可以改进，如使用禁忌搜索法*/

if(metro[i][k]==1r_color[k]==r_color[i])

break;

if(k=i)

break;

}

}

void main()

{

int r_color[N]={0};

int t_color[N]={0};

int i;

int start;/*着色的起点*/

int metro[N][N]={{0},

{0,1,1,1,1,1,1},

{0,1,1,1,1},

{0,1,1,1,0,0,1},

{0,1,1,0,1,1},

{0,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1},

{0,1,0,1,0,1,1,1,1,1},

{0,0,0,0,0,0,1,1,1},

{0,0,0,0,0,0,1,1,1,1,0,0,1},

{0,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1},

{0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1},

{0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},

{0,0,0,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,1,1},

{0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1},

{0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1},

{0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1,0,1},

{0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,1},

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1},

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1},

{0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,1,1,1},

{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1}};

allcolor[0]=1;allcolor[1]=2;allcolor[2]=3;allcolor[3]=4;/*选色顺序，顺序不同，结果不同*/

start=1;

/* clrscr();*/

printf("\nAll color is:\n");

for(i=0;i4;i++)/*当前选色顺序*/

printf("%d ",allcolor[i]);

go(metro,r_color,20,1);

printf("\nFirst method:\n");

for(i=1;i=20;i++)

printf("%3d",r_color[i]);

color(metro,t_color,20,start);

printf("\nSecond method:\n");

printf("\nAnd the start metro is:%d\n",start);

for(i=1;i=20;i++)

printf("%3d",t_color[i]);

}

说是人性化着色，其实还有一个问题没有考虑，那就是操作员跳跃式着色，就像大家玩“扫雷”游戏一样。其实也容易实现，可以像定义选色顺序一样定义着色顺序。

java地图着色问题

建议百度搜索地图着色问题，这是一个数学问题，印象中应该是个图的问题，所以你要先会用数学方式解决，其次才是用程序代码描述出来。

网页名称：地图着色java代码 地图着色需要几种颜色
URL分享：http://azwzsj.com/article/ddgiepe.html