日期:2014-05-20 浏览次数:20731 次
import java.util.*; import java.awt.*; public class Test { public static final int HEIGHT = 5; public static final int WIDTH = 5; public static ArrayList<Point> path = new ArrayList<Point>(); public static void search(boolean[][] map, int y, int x) { if (map[y][x]) { return; } else { map[y][x] = true; path.add(new Point(x, y)); if (isFull(map)) { StringBuilder strBuf = new StringBuilder(); for (Point p : path) { strBuf.append("(" + p.y); strBuf.append("," + p.x + ")"); strBuf.append(" -> "); } strBuf.setLength(strBuf.length() - 4); System.out.println(strBuf); } int newY; int newX; //UP newY = y - 1; if (newY >= 0) { search(map, newY, x); } //DOWN newY = y + 1; if (newY < HEIGHT) { search(map, newY, x); } //LEFT newX = x - 1; if (newX >= 0) { search(map, y, newX); } //RIGHT newX = x + 1; if (newX < WIDTH) { search(map, y, newX); } map[y][x] = false; path.remove(path.size() - 1); } } public static boolean isFull(boolean[][] map) { int k = 0; for (int i = 0; i < HEIGHT; i++) { for (int j = 0; j < WIDTH; j++) { if (map[i][j]) { k++; } } } return k == 25; } public static void main(String[] args) { boolean[][] map = { {false, false, false, false, false}, {false, false, false, false, false}, {false, false, false, false, false}, {false, false, false, false, false}, {false, false, false, true, false} }; for (int i = 0; i < HEIGHT; i++) { for (int j = 0; j < WIDTH; j++) { if (! map[i][j]) { search(map, i, j); } } } } }
------解决方案--------------------
Keeya厉害呀!
将图黑白染色,X表示黑,O表示白,I表示红点
XOXOX
OXOXO
XOXOX
OXOXO
XOXIX
可知每经过一个黑点,之后必定经过一个白点。同样每经过1个白点之后必然经过一个黑点。
不论以黑点还是白点作为起点,经过的黑点总数同白点总数之差不超过1。
而Lz给的图中,黑点比白点多了2个,因此无法一笔画完。