日期:2014-05-20 浏览次数:20892 次
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个,因此无法一笔画完。