经典四色问题,用贪心法, java求解,我的不对,请大家帮忙挑挑毛病哈,又卡住了…… 谢谢!
"src/T12/map"
文件map。
4 - number of lands, 5 - borders, 01 代表land 0 和land 1有border 。。。。。
代码:
package T12;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
public class N37 {
private static void fourColorMap(String dir) {
try { // read in file
BufferedReader in = new BufferedReader(new FileReader(dir));
String line = "";
// construct border[j], land & color
int numLand = Integer.parseInt(in.readLine());
int[] land = new int[numLand];
// init land
for(int i = 0; i < land.length; i ++) {
land_i = 0;
}
int numBorder = Integer.parseInt(in.readLine());
boolean[][] border = new boolean[numBorder][numBorder];
// init border all false
for(int i = 0; i < border.length; i ++) {
for(int j = 0; j < border.length; j ++) {
border[j] = false;
}
}
// read in borders from file
for(int i = 0; i < border.length; i ++) {
for(int j = 0; j < border.length; j ++) {
while((line = in.readLine()) != null) {
int m = Integer.parseInt(String.valueOf(line.charAt(0)));
int n = Integer.parseInt(String.valueOf(line.charAt(1)));
//System.out.println("m = " + m + ", n = " + n);
border[m][n] = true;
}
}
}
// init color array, 4 colors
boolean[] color = new boolean[4];
for(int i = 0; i < color.length; i ++) {
color_i = false;
}
int n = land.length;
for(int i = 0; i < n; i ++) {
for(int j = 0; j < n; j ++) {
if(border[j] && land[j] != 0) {
color[land[j]] = true;
}
}
for(int j = 1; j < color.length; j ++) {
if(color[j] == false) {
land_i = j;
break;
}
}
}
print(land);
//
// for(int i = 0; i < color.length; i ++) {
// System.out.println(color);
// }
// for(int i = 0; i < border.length; i ++) {
// for(int j = 0; j < border.length; j ++) {
// System.out.print(border[j] + " ");
// }
// }
// System.out.println("land size " + land.length + " border: " + border.length);
} catch(IOException e) {
e.printStackTrace(System.err);
System.exit(1);
}
}
public static void main(String[] args) {
String DIR = "src/T12/map";
fourColorMap(DIR);
}
private static void print(int[] a) {
for(int i = 0; i < a.length; i ++) {
System.out.print(a + " ");
}
}
}
文件map。
4 - number of lands, 5 - borders, 01 代表land 0 和land 1有border 。。。。。
代码:
4
5
01
02
12
13
23
最后编辑: 2018-02-17