地图着色可以使用回溯的方法进行解决。
我们提供的服务有：网站设计、成都网站建设、微信公众号开发、网站优化、网站认证、佳木斯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写一个地图编辑器
记得媒体在采访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];
}
}
从一个省开始，给它涂上任意一种颜色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]);
}
说是人性化着色，其实还有一个问题没有考虑，那就是操作员跳跃式着色，就像大家玩“扫雷”游戏一样。其实也容易实现，可以像定义选色顺序一样定义着色顺序。
建议百度搜索地图着色问题，这是一个数学问题，印象中应该是个图的问题，所以你要先会用数学方式解决，其次才是用程序代码描述出来。
