?
〇 ?X ?〇 〇 〇
〇 〇 〇 〇 〇
〇 〇 〇 〇 〇
〇 〇 〇 〇 〇
〇 〇 〇 〇 〇
不过X点，把所有的圈连起来，不能重复，不能斜连，不能跳圈
?
本人用了游戏寻路算法做了一个程序，没有解出答案，如果差一个圈的有1064个解法。欢迎高手们解答
?
import java.util.ArrayList;
/**
* @author xtiger (xtiger@microsoul.com) 2015-09-09 23:39
*/
public class Game {
private static int[][] t = new int[7][7]; //记录圈子，外围多加一圈，免得判断 ，0：可以走，1：走过，2：不可走
private static int r[] = new int[25]; //记录结果
private static int i = 2; //当前圈子的x
private static int j = 1; //当前圈子的y
private static int idx = 0;
private static int bb = 1;
private static ArrayList<String> die = new ArrayList<String>(); //记录走不通的路线
public static void main(String[] args) {
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 7; j++) {
if (i == 0) {
t[i][j] = 2;
}
if (i == 6) {
t[i][j] = 2;
}
if (j == 0) {
t[i][j] = 2;
}
if (j == 6) {
t[i][j] = 2;
}
}
}
t[1][2] = 2;
t[1][1] = 2;
t[2][1] = 2;
r[idx++] = 11;
r[idx++] = 21;
while (true) {
if (up() == 1) continue;
if (right() == 1) continue;
if (down() == 1) continue;
if (left() == 1) continue;
back();
int b = 0;
for (int x = 1; x <= 5; x++) {
for (int y = 1; y <= 5; y++) {
b += t[x][y];
}
}
if (b == 26) {
echo1();
continue;
}
if (b == 28) break;
}
System.out.println("GOOOOOOOOOOD---------------");
echo1();
}
private static int up() {
if (checkDie((i - 1) * 10 + j)) {
return 0;
}
if (t[i - 1][j] == 0) {
r[idx++] = (i - 1) * 10 + j;
t[i - 1][j] = 1;
i--;
return 1;
}
return -1;
}
private static int right() {
if (checkDie(i * 10 + j + 1)) {
return 0;
}
if (t[i][j + 1] == 0) {
r[idx++] = i * 10 + j + 1;
t[i][j + 1] = 1;
j++;
return 1;
}
return -1;
}
private static int down() {
if (checkDie((i + 1) * 10 + j)) {
return 0;
}
if (t[i + 1][j] == 0) {
r[idx++] = (i + 1) * 10 + j;
t[i + 1][j] = 1;
i++;
return 1;
}
return -1;
}
private static int left() {
if (checkDie(i * 10 + j - 1)) {
return 0;
}
if (t[i][j - 1] == 0) {
r[idx++] = i * 10 + j - 1;
t[i][j - 1] = 1;
j--;
return 1;
}
return -1;
}
private static boolean checkDie(int next) {
return die.contains(getPath(idx) + next + "/");
}
private static boolean back() {
String p = getPath(idx);
if (!die.contains(p))
die.add(getPath(idx));
if (idx > 0) {
idx--;
if (t[r[idx] / 10][r[idx] % 10] == 1) {
t[r[idx] / 10][r[idx] % 10] = 0;
}
}
if (idx > 0) {
i = r[idx - 1] / 10;
j = r[idx - 1] % 10;
return false;
}
return true;
}
private static String getPath(int pos) {
StringBuilder s = new StringBuilder();
for (int x = 0; x < pos; x++) {
s.append(r[x]).append("/");
}
return s.toString();
}
private static String getPos(int v) {
for (int x = 1; x <= 25; x++) {
if (r[x - 1] == v) return "" + (x + 10);
}
return " ";
}
private static void echo1() {
System.out.println();
System.out.println((bb++) + ". -----------");
for (int x = 1; x <= 5; x++) {
for (int y = 1; y <= 5; y++) {
System.out.print(getPos(10 * x + y) + " ");
}
System.out.println();
}
}
}
?
?
?如果差一个圈的有1064个解法，展示一部分：
1. ----------- 11 15 16 17 12 13 14 18 31 30 25 24 19 32 29 26 23 20 33 28 27 22 21 2. ----------- 11 15 16 17 12 13 14 18 31 32 25 24 19 30 33 26 23 20 29 28 27 22 21 3. ----------- 11 15 16 17 12 13 14 18 33 32 25 24 19 30 31 26 23 20 29 28 27 22 21 4. ----------- 11 15 16 17 12 13 14 18 29 28 25 24 19 30 27 26 23 20 31 32 33 22 21
?
原文：http://openxtiger.iteye.com/blog/2242585