面试遇到一个算法问题，寻求思路

---

更新【2016-05-13 12:10】
这是我用穷举的方式实现的，达不到最快的方法

主类：SortBlock.java

package demo;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class SortBlock {

    public static void main(String[] args) {
        Random random = new Random();

        int count = 0;

        Block[][] blocks = {
                { new Block(ColorEnum.Y), new Block(ColorEnum.R), new Block(ColorEnum.B), new Block(ColorEnum.B) },
                { new Block(ColorEnum.R), new Block(ColorEnum.R), new Block(ColorEnum.B), new Block(ColorEnum.B) },
                { new Block(ColorEnum.R), new Block(ColorEnum.R), new Block(ColorEnum.B), new Block(ColorEnum.B) },
                { new Block(ColorEnum.R), new Block(ColorEnum.R), new Block(ColorEnum.B), new Block(ColorEnum.B) } };

        System.out.println("开始：");
        printBlock(blocks);

        while (!isFinish(blocks)) {

            String[] position = getMoveBlockPosition(blocks).split("-");
            int i = Integer.parseInt(position[0]);
            int j = Integer.parseInt(position[1]);

            int derection = getMoveDirection(random, i, j);

            // System.out.println("第" + count + "步 - 移动位置[" + i + "," + j + "] -
            // 方向[" + direction + "]");
            blocks = updateBlock(blocks, derection, i, j);

            count++;
        }

        System.out.println("");
        System.out.println("");
        System.out.println("");
        System.out.println("总计：" + count + "步");
        System.out.println("");
        System.out.println("");
        System.out.println("");
        System.out.println("结果：");
        printBlock(blocks);

    }

    // 打印所有块
    public static void printBlock(Block[][] blocks) {
        for (int i = 0; i < blocks.length; i++) {
            for (int j = 0; j < blocks[i].length; j++) {
                if (j == blocks[i].length - 1) {
                    System.out.print(blocks[i][j].blockColor);
                } else {
                    System.out.print(blocks[i][j].blockColor + " - ");
                }
            }
            System.out.println("");
        }
    }

    // 更新黄色块移动后所有块的位置
    public static Block[][] updateBlock(Block[][] blocks, int derection, int i, int j) {
        ColorEnum temp;
        if (derection == 0) {
            temp = blocks[i][j - 1].blockColor;
            blocks[i][j - 1].blockColor = ColorEnum.Y;
            blocks[i][j].blockColor = temp;
        } else if (derection == 1) {
            temp = blocks[i - 1][j].blockColor;
            blocks[i - 1][j].blockColor = ColorEnum.Y;
            blocks[i][j].blockColor = temp;
        } else if (derection == 2) {
            temp = blocks[i][j + 1].blockColor;
            blocks[i][j + 1].blockColor = ColorEnum.Y;
            blocks[i][j].blockColor = temp;
        } else if (derection == 3) {
            temp = blocks[i + 1][j].blockColor;
            blocks[i + 1][j].blockColor = ColorEnum.Y;
            blocks[i][j].blockColor = temp;
        }
        return blocks;
    }

    // 随机获取黄色块的可移动方向
    public static int getMoveDirection(Random random, int i, int j) {
        // 左边：0
        // 上边：1
        // 右边：2
        // 下边：3

        List<Integer> arrs = new ArrayList<>();
        if (i == 0) {
            if (j == 0) {
                arrs.add(2);
                arrs.add(3);
            } else if (j == 3) {
                arrs.add(0);
                arrs.add(3);
            } else {
                arrs.add(0);
                arrs.add(2);
                arrs.add(3);
            }

        } else if (i == 3) {
            if (j == 0) {
                arrs.add(1);
                arrs.add(2);
            } else if (j == 3) {
                arrs.add(0);
                arrs.add(1);
            } else {
                arrs.add(0);
                arrs.add(1);
                arrs.add(2);
            }
        } else {
            if (j == 0) {
                arrs.add(1);
                arrs.add(2);
                arrs.add(3);
            } else if (j == 3) {
                arrs.add(0);
                arrs.add(1);
                arrs.add(3);
            } else {
                arrs.add(0);
                arrs.add(1);
                arrs.add(2);
                arrs.add(3);
            }
        }
        return arrs.get(random.nextInt(arrs.size()));
    }

    // 获取黄色块的当前位置
    public static String getMoveBlockPosition(Block[][] blocks) {
        for (int i = 0; i < blocks.length; i++) {
            for (int j = 0; j < blocks[i].length; j++) {
                if (blocks[i][j].canMove()) {
                    return i + "-" + j;
                }
            }
        }
        return null;
    }

    // 判断是否达到最终的效果
    public static boolean isFinish(Block[][] blocks) {
        if (blocks[0][0].blockColor.equals(ColorEnum.Y) && blocks[0][1].blockColor.equals(ColorEnum.B)
                && blocks[0][2].blockColor.equals(ColorEnum.R) && blocks[0][3].blockColor.equals(ColorEnum.B)
                && blocks[1][0].blockColor.equals(ColorEnum.B) && blocks[1][1].blockColor.equals(ColorEnum.R)
                && blocks[1][2].blockColor.equals(ColorEnum.B) && blocks[1][3].blockColor.equals(ColorEnum.R)
                && blocks[2][0].blockColor.equals(ColorEnum.R) && blocks[2][1].blockColor.equals(ColorEnum.B)
                && blocks[2][2].blockColor.equals(ColorEnum.R) && blocks[2][3].blockColor.equals(ColorEnum.B)
                && blocks[3][0].blockColor.equals(ColorEnum.B) && blocks[3][1].blockColor.equals(ColorEnum.R)
                && blocks[3][2].blockColor.equals(ColorEnum.B) && blocks[3][3].blockColor.equals(ColorEnum.R)) {
            return true;
        }
        return false;
    }
}

工具类：Block.java

package demo;

public class Block {
    ColorEnum blockColor;

    public Block(ColorEnum blockColor) {
        this.blockColor = blockColor;
    }

    public boolean canMove() {
        if (this.blockColor.equals(ColorEnum.Y)) {
            return true;
        }
        return false;
    }
}

工具类：ColorEnum.java

package demo;

public enum ColorEnum {
    Y, R, B
}

---

其实这个你每天都见着的。不要把黄色看做方块，直接看成是一个空，有了空就可以移动那些方块。这样一看有没有想到是什么东西？其实就是手机桌面，然后排列桌面图标。为了好好解释下，我还特意把我的手机apps排了一下。不知道你小时候有没有玩过这种拼图，4x4只有15个方块。

---

我记得大三的时候人工智能讲了个A*算法，可能可以用在这题上。我说个思路吧，每次都试着移动上下左右四个方向，然后计算移动后黄色所在位置与目标位置的距离，记为dis，还有当前位置颜色正确的方块数，记为count，然后比较四个方向的这两个值，往dis最小，count最大的方向移动

---

应该用深度搜索和广度搜索可以做到吧。不过，我想它的数据空间会比较大吧，毕竟得枚举非常非常多的走法。有大神解决这个问题吗？上代码让大家瞧瞧。

---

编码一个结构保存状态，用 (x,y) 标识黄块的位置，为了方便，用一个整数的前 16 位压缩每个位置是蓝还是红。

这样的话所有的状态一共是 4 × 4 × 2¹⁶ = 1048576。暴力深搜可以在一秒之内得到结果。每种状态的空间也只要几个比特，总空间也不是问题。