日期:2014-05-20  浏览次数:20701 次

谁来挑战一下?

这是今天一个朋友问我的问题,我没解决,不知道有没有牛人可以挑战一下。
规则是这样的,用JAVA实现。在这张图中,一笔将所有黑点连接起来,不能连接红点。连接的黑点不能重复。
每个黑点只能上下,左右连接,不能斜着连接。找到该路后,输出路径(出发点---结束点)。


------解决方案--------------------
我用递归的方法试了下,表示没有这条路径
Java code

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个,因此无法一笔画完。

探讨

这个可以用着色来证明是无解的

------解决方案--------------------
其实有另一种思路来证明,红点右边的黑点只能与其上方的黑点相连,这个黑点必为起点或终点,如想一笔连完,这要就需要另外一个只能外连一个点的黑点存在,显然不存在这样的黑点,所以无解。