欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

使用dfs、bfs和邻接线性表解决9枚硬币翻转问题

程序员文章站 2024-03-26 09:35:41
...

问题描述:
在一个3*3的矩阵中,每一个格子表示一枚硬币,其中一些硬币正面朝上,另一些正面朝下。需要经过一些移动,使得所有的硬币都正面朝下。
而每一次移动的规则是这样的:每次翻转一个硬币,那么这枚硬币的上下左右的硬币也都要重新翻转一次(不包括对角线相邻的)。
经过尽量少的翻转次数,使得所有硬币都正面朝下,那么结束。

先说下大致思路
先用递归算法生成9枚硬币正反的所有可能,一共有2^9种。把512种可能作为图的顶点。
n=0从第一枚硬币开始(这个无关紧要)

/** 一维数组保存硬币 */
private char[] coinChar = new char[9];

/** 二维数组保存硬币 */
private List<char[][]> verticesCoinChar = new ArrayList<>();

/** 存储顶点 */
private List<String> vertices = new ArrayList<>();

/** 邻接表 */
private List<List<Edge>> neighbors = new ArrayList<>();

public void positiveAndNegative(int n) {
    if(n >= 9) {
        vertices.add(String.valueOf(coinChar));
        verticesCoinChar.add(oneToTwoDimensional(coinChar));
        neighbors.add(new ArrayList<>());
        return;
    }
    for(int i = 0; i < 2; i++) {
        coinChar[n] = coinChar[n] == 'H' ? 'T' : 'H';
        int k = n + 1;
        positiveAndNegative(k);
    }
}

接下来构建邻接表,令H为正面,T为反面。大致思路就是对512种可能进行遍历。把9枚硬币保存到二维数组,然后依次对硬币逐一进行翻转,相应的相邻的硬币也同时翻转,得到的结果,在拿到存储512种可能的数组进行判断。把符合的可能保存到该邻接线性表中。

/**
 * 构建邻接表
 */
private void structureNeighbors() {
    for(int k = 0; k < verticesCoinChar.size(); k++) {
        for(int i = 1; i <= 3; i++) {
            for(int j = 1; j <= 3; j++) {
                char[][] temp = arrayEnlarge(verticesCoinChar.get(k));
                temp[i][j] = temp[i][j] == 'H' ? 'T' : 'H';
                if(temp[i-1][j] != ' ') {
                    temp[i-1][j] = temp[i-1][j] == 'H' ? 'T' : 'H';
                }
                if(temp[i+1][j] != ' ') {
                    temp[i+1][j] = temp[i+1][j] == 'H' ? 'T' : 'H';
                }
                if(temp[i][j-1] != ' ') {
                    temp[i][j-1] = temp[i][j-1] == 'H' ? 'T' : 'H';
                }
                if(temp[i][j+1] != ' ') {
                    temp[i][j+1] = temp[i][j+1] == 'H' ? 'T' : 'H';
                }
                String str = convertString(temp);
                Edge edge = new Edge(k, vertices.indexOf(str));
                if(!neighbors.get(edge.u).contains(edge)) {
                    neighbors.get(edge.u).add(edge);
                }
            }
        }
    }
}

邻接表打印出来是这样的(截取一小部分)

HHHHHHHHH (0): (0, 416) (0, 464) (0, 200) (0, 308) (0, 186) (0, 89) (0, 38) (0, 23) (0, 11) 
HHHHHHHHT (1): (1, 417) (1, 465) (1, 201) (1, 309) (1, 187) (1, 88) (1, 39) (1, 22) (1, 10) 
HHHHHHHTH (2): (2, 418) (2, 466) (2, 202) (2, 310) (2, 184) (2, 91) (2, 36) (2, 21) (2, 9) 
HHHHHHHTT (3): (3, 419) (3, 467) (3, 203) (3, 311) (3, 185) (3, 90) (3, 37) (3, 20) (3, 8) 
HHHHHHTHH (4): (4, 420) (4, 468) (4, 204) (4, 304) (4, 190) (4, 93) (4, 34) (4, 19) (4, 15) 
HHHHHHTHT (5): (5, 421) (5, 469) (5, 205) (5, 305) (5, 191) (5, 92) (5, 35) (5, 18) (5, 14) 
HHHHHHTTH (6): (6, 422) (6, 470) (6, 206) (6, 306) (6, 188) (6, 95) (6, 32) (6, 17) (6, 13) 
HHHHHHTTT (7): (7, 423) (7, 471) (7, 207) (7, 307) (7, 189) (7, 94) (7, 33) (7, 16) (7, 12) 
HHHHHTHHH (8): (8, 424) (8, 472) (8, 192) (8, 316) (8, 178) (8, 81) (8, 46) (8, 31) (8, 3) 
HHHHHTHHT (9): (9, 425) (9, 473) (9, 193) (9, 317) (9, 179) (9, 80) (9, 47) (9, 30) (9, 2) 
HHHHHTHTH (10): (10, 426) (10, 474) (10, 194) (10, 318) (10, 176) (10, 83) (10, 44) (10, 29) (10, 1) 
HHHHHTHTT (11): (11, 427) (11, 475) (11, 195) (11, 319) (11, 177) (11, 82) (11, 45) (11, 28) (11, 0) 
HHHHHTTHH (12): (12, 428) (12, 476) (12, 196) (12, 312) (12, 182) (12, 85) (12, 42) (12, 27) (12, 7)
                                         .
                                         .
                                         .

下面是整个代码的核心,dfs。感觉效率一般般(感觉算法写的很复杂,可能几天回来看就不知道写的是什么了),虽然经过优化了(但感觉整体算法还是不太妥,可能智商不够用了)。
解决这个问题其实最好的方法是bfs(思路也比较简单),但个人比较喜欢dfs,也用dfs实现一遍。

/** 查找顶点顺序 */
private List<String> searchOrder = new ArrayList<>();

/** 保存最少翻转次数的所有可能 */
private Map<Integer, List<String[]>> map = new HashMap<>();

/** 是否已经被查找 */
private boolean[] isVisited;

private int min = 512;

public void dfs(int v) {
    isVisited = new boolean[vertices.size()];
    int sum = 0;
    dfs(v, sum);
}

private boolean dfs(int u, int sum) {
    //sum表示步骤,如果步骤大于最小步骤,则返回
    if(++sum > min) {
        return true;
    }
    searchOrder.add(vertices.get(u));
    isVisited[u] = true;
    for(Edge e : neighbors.get(u)) {
        //如果已经查找过该顶点
        if(isVisited[e.v]) {
            continue;
        }
        //找到全都是反面的可能,并把保存步骤
        if(OPPOSITE.equals(vertices.get(e.v))) {
            int temp = min;
            //更新最小步骤的值
            min = sum;
            String[] str = searchOrder.toArray(new String[searchOrder.size() + 1]);
            str[str.length - 1] = OPPOSITE;
            if(map.get(min) != null) {
                map.get(min).add(str);
            } else {
                map.remove(temp);
                List<String[]> list = new ArrayList<>();
                list.add(str);
                map.put(min, list);
            }
            //该顶点对应的邻接表不需要在继续查询。
            break;
        }
        //如果为true,继续查找,如果为false跳出进行回溯
        if(!dfs(e.v, sum)) {
            break;
        }
    }
    //回溯
    if(searchOrder.size() > 0) {
        //回溯的时候需要把该标记去掉,这样后面的顶点才能访问到它
        isVisited[u] = false;
        //把不合适的顶点去除
        searchOrder.remove(searchOrder.size() - 1);
    }
    return true;
}

下面使用bfs,整体算法的效率比dfs高了很多,主要的思想就是逐层查找(只要把parent数组和parentMap之间的关系弄明白就好了)。如果查找到满足就不需要继续往下查找了,即不用继续深入查找。因为最先查找到的就是最少步骤的情况。接下来只需要继续查找同步骤的情况即可,代码写的还是很杂乱(需要进行优雅化)。

/** 保存bfs查找到的所有情况 */
private List<List<String>> list = new ArrayList<>();

/** 保存节点的所有父节点 */
private Map<Integer, List<Integer>> parentMap = new HashMap<>();

/**
 * bfs为什么不像dfs使用isVisited来标记已经访问节点,而是用parent数组来判断。
 * 举个例子:像这个HTTHHTHTT 可以有HHTTTHHHT或者HTHHTHHTH通过一次翻转变成它。
 * 所以用isVisited就会导致结果只有一种。即经HHTTTHHHT访问到HTTHHTHTT后,就不能继续访问了。
 * 所以用parent来替代。但是使用parent有个缺陷就是后面的父节点会把该节点原来的父节点替换。
 * 原来的父节点并还没使用在。所以需要新增加parentMap来给节点动态存储父节点。当一个使用完后
 * 就去除,并更新父节点。
 *
 * @param v
 */
public void bfs(int v) {
    int[] parent = new int[vertices.size()];
    for(int i = 0; i < parent.length; i++) {
        parent[i] = -1;
    }
    LinkedList<Integer> queue = new LinkedList<>();
    queue.offer(v);
    boolean flag = false;
    while(!queue.isEmpty()) {
        int u = queue.poll();
        for(Edge e : neighbors.get(u)) {
            if(OPPOSITE.equals(vertices.get(e.v))) {
                parent[e.v] = u;
                ArrayList<String> path = new ArrayList<>();
                v = vertices.indexOf(OPPOSITE);
                do {
                    path.add(vertices.get(v));
                    v = parent[v];
                } while(v != -1);
                list.add(path);
                //如果查找到,就没必要继续深入了,因为这就是最少步骤的方法。
                flag = true;
                List<Integer> list = parentMap.get(u);
                //当前父节点已使用完毕,去除。但如果父节点只有一个就不去除。
                if(list.size() > 1) {
                    list.remove(0);
                }
                //重新设置父节点
                parent[u] = list.get(0);
                break;
            }
            if(!flag) {
                //保存当前顶点的父亲节点的父亲节点....依次类推,这样既可以避免重复查询,又可以保证多次查询。
                List<Integer> list = new ArrayList<>();
                v = u;
                while(v != -1) {
                    list.add(v);
                    v = parent[v];
                }
                if(!list.contains(e.v)) {
                    queue.offer(e.v);
                    //这里做个判断,防止后面节点的改变当前节点的父类
                    if(parent[e.v] == -1) {
                        parent[e.v] = u;
                    }
                    parentMap.computeIfAbsent(e.v, k -> new ArrayList<>());
                    //添加当前节点的父节点,可能有多个。到时候需要一个一个来取值。
                    parentMap.get(e.v).add(u);
                }
            }
        }
    }
}

接着,输入代查询的硬币。例如输入HHHTTTHHH,打印它翻转到TTTTTTTTT最少的步骤。
完整代码如下

package com.aekc.algorithm;

import com.aekc.algorithm.graph.UnweightedGraph;

import java.util.*;

public class CoinOpposite {

    /** 一维数组保存硬币 */
    private char[] coinChar = new char[9];

    /** 二维数组保存硬币 */
    private List<char[][]> verticesCoinChar = new ArrayList<>();

    /** 存储顶点 */
    private List<String> vertices = new ArrayList<>();

    /** 邻接表 */
    private List<List<Edge>> neighbors = new ArrayList<>();

    /** 全都是反面 */
    private static final String OPPOSITE = "TTTTTTTTT";

    public class Edge {

        /** 起始顶点 */
        public int u;

        /** 结束顶点 */
        public int v;

        public Edge(int u, int v) {
            this.u = u;
            this.v = v;
        }

        @Override
        public boolean equals(Object o) {
            return u == ((Edge) o).u && v == ((Edge) o).v;
        }
    }

    public CoinOpposite() {
        positiveAndNegative(0);
        structureNeighbors();
    }

    private String convertString(char[][] array) {
        StringBuilder stringBuilder = new StringBuilder();
        for(int i = 1; i <= 3; i++) {
            for(int j = 1; j <= 3; j++) {
                stringBuilder.append(array[i][j]);
            }
        }
        return stringBuilder.toString();
    }

    /**
     * 构建邻接表
     */
    private void structureNeighbors() {
        for(int k = 0; k < verticesCoinChar.size(); k++) {
            for(int i = 1; i <= 3; i++) {
                for(int j = 1; j <= 3; j++) {
                    char[][] temp = arrayEnlarge(verticesCoinChar.get(k));
                    temp[i][j] = temp[i][j] == 'H' ? 'T' : 'H';
                    if(temp[i-1][j] != ' ') {
                        temp[i-1][j] = temp[i-1][j] == 'H' ? 'T' : 'H';
                    }
                    if(temp[i+1][j] != ' ') {
                        temp[i+1][j] = temp[i+1][j] == 'H' ? 'T' : 'H';
                    }
                    if(temp[i][j-1] != ' ') {
                        temp[i][j-1] = temp[i][j-1] == 'H' ? 'T' : 'H';
                    }
                    if(temp[i][j+1] != ' ') {
                        temp[i][j+1] = temp[i][j+1] == 'H' ? 'T' : 'H';
                    }
                    String str = convertString(temp);
                    Edge edge = new Edge(k, vertices.indexOf(str));
                    if(!neighbors.get(edge.u).contains(edge)) {
                        neighbors.get(edge.u).add(edge);
                    }
                }
            }
        }
    }

    private char[][] oneToTwoDimensional(char[] coinChar) {
        int k = 0;
        char[][] chars = new char[3][3];
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                chars[i][j] = coinChar[k++];
            }
        }
        return chars;
    }

    private char[][] arrayEnlarge(char[][] array) {
        char[][] chars = new char[5][5];
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                chars[i+1][j+1] = array[i][j];
            }
        }
        return chars;
    }

    /**
     * 生成9枚硬币正反的所有可能
     * @param n
     */
    public void positiveAndNegative(int n) {
        if(n >= 9) {
            vertices.add(String.valueOf(coinChar));
            verticesCoinChar.add(oneToTwoDimensional(coinChar));
            neighbors.add(new ArrayList<>());
            return;
        }
        for(int i = 0; i < 2; i++) {
            coinChar[n] = coinChar[n] == 'H' ? 'T' : 'H';
            int k = n + 1;
            positiveAndNegative(k);
        }
    }

    public void printEdges() {
        for(int u = 0; u < neighbors.size(); u++) {
            System.out.print(vertices.get(u) + " (" + u + "): ");
            for(Edge e : neighbors.get(u)) {
                System.out.print("(" + e.u + ", " + e.v + ") ");
            }
            System.out.println();
        }
    }

    /** 查找顺序 */
    private List<String> searchOrder = new ArrayList<>();

    /** 保存最少翻转次数的所有可能 */
    private Map<Integer, List<String[]>> map = new HashMap<>();

    /** 是否已经被查找 */
    private boolean[] isVisited;

    private int min = 512;

    public void dfs(int v) {
        isVisited = new boolean[vertices.size()];
        int sum = 0;
        dfs(v, sum);
    }

    private boolean dfs(int u, int sum) {
        //sum表示步骤,如果步骤大于最小步骤,则返回
        if(++sum > min) {
            return true;
        }
        searchOrder.add(vertices.get(u));
        isVisited[u] = true;
        for(Edge e : neighbors.get(u)) {
            //如果已经查找过该顶点
            if(isVisited[e.v]) {
                continue;
            }
            //找到全都是反面的可能,并把保存步骤
            if(OPPOSITE.equals(vertices.get(e.v))) {
                int temp = min;
                //更新最小步骤的值
                min = sum;
                String[] str = searchOrder.toArray(new String[searchOrder.size() + 1]);
                str[str.length - 1] = OPPOSITE;
                if(map.get(min) != null) {
                    map.get(min).add(str);
                } else {
                    map.remove(temp);
                    List<String[]> list = new ArrayList<>();
                    list.add(str);
                    map.put(min, list);
                }
                //该顶点对应的邻接表不需要在继续查询。
                break;
            }
            //如果为true,继续查找,如果为false跳出进行回溯
            if(!dfs(e.v, sum)) {
                break;
            }
        }
        //回溯
        if(searchOrder.size() > 0) {
            //回溯的时候需要把该标记去掉,这样后面的顶点才能访问到它
            isVisited[u] = false;
            //把不合适的顶点去除
            searchOrder.remove(searchOrder.size() - 1);
        }
        return true;
    }

    //--------------------下面是bfs代码-------------------

    /** 保存bfs查找到的所有情况 */
    private List<List<String>> list = new ArrayList<>();

    /** 保存节点的所有父节点,不包括祖父节点等辈份更高的节点 */
    private Map<Integer, List<Integer>> parentMap = new HashMap<>();

    /**
     * bfs为什么不像dfs使用isVisited来标记已经访问节点,而是用parent数组来判断。
     * 举个例子:像这个HTTHHTHTT 可以有HHTTTHHHT或者HTHHTHHTH通过一次翻转变成它。
     * 所以用isVisited就会导致结果只有一种。即经HHTTTHHHT访问到HTTHHTHTT后,就不能继续访问了。
     * 所以用parent来替代。但是使用parent有个缺陷就是后面的父节点会把该节点原来的父节点替换。
     * 原来的父节点并还没使用在。所以需要新增加parentMap来给节点动态存储父节点。当一个使用完后
     * 就去除,并更新父节点。
     *
     * @param v
     */
    public void bfs(int v) {
        int[] parent = new int[vertices.size()];
        for(int i = 0; i < parent.length; i++) {
            parent[i] = -1;
        }
        LinkedList<Integer> queue = new LinkedList<>();
        queue.offer(v);
        boolean flag = false;
        while(!queue.isEmpty()) {
            int u = queue.poll();
            for(Edge e : neighbors.get(u)) {
                if(OPPOSITE.equals(vertices.get(e.v))) {
                    parent[e.v] = u;
                    ArrayList<String> path = new ArrayList<>();
                    v = vertices.indexOf(OPPOSITE);
                    do {
                        path.add(vertices.get(v));
                        v = parent[v];
                    } while(v != -1);
                    list.add(path);
                    //如果查找到,就没必要继续深入了,因为这就是最少步骤的方法。
                    flag = true;
                    List<Integer> list = parentMap.get(u);
                    //当前父节点已使用完毕,去除。但如果父节点只有一个就不去除。
                    if(list.size() > 1) {
                        list.remove(0);
                    }
                    //重新设置父节点
                    parent[u] = list.get(0);
                    break;
                }
                if(!flag) {
                    //保存当前顶点的父亲节点的父亲节点....依次类推,这样既可以避免重复查询,又可以保证多次查询。
                    List<Integer> list = new ArrayList<>();
                    v = u;
                    while(v != -1) {
                        list.add(v);
                        v = parent[v];
                    }
                    if(!list.contains(e.v)) {
                        queue.offer(e.v);
                        //这里做个判断,防止后面节点的改变当前节点的父类
                        if(parent[e.v] == -1) {
                            parent[e.v] = u;
                        }
                        parentMap.computeIfAbsent(e.v, k -> new ArrayList<>());
                        //添加当前节点的父节点,可能有多个。到时候需要一个一个来取值。
                        parentMap.get(e.v).add(u);
                    }
                }
            }
        }
    }

    /** 待判断的硬币 */
    private static final String DEFAULT = "HHTTHHHHH";

    public static void main(String[] args) {
    System.out.println("-----------dfs-----------");
        CoinOpposite coinOpposite = new CoinOpposite();
        coinOpposite.dfs(coinOpposite.vertices.indexOf(DEFAULT));
        List<String[]> list = coinOpposite.map.get(coinOpposite.min);
        for(String[] strs : list) {
            for(String s : strs) {
                System.out.println(s);
            }
            System.out.println();
        }

        System.out.println("-----------bfs-----------");

        CoinOpposite coinOpposite2 = new CoinOpposite();
        coinOpposite2.bfs(coinOpposite.vertices.indexOf(DEFAULT));
        for(List<String> stringList : coinOpposite2.list) {
            for(int i = stringList.size() - 1; i >= 0; i--) {
                System.out.println(stringList.get(i));
            }
            System.out.println();
        }
        //coinOpposite.printEdges();
    }
}

输入HHHTTTHHH,示例输出。一共两种情况,最少需要2步。

-----------dfs-----------
HHHTTTHHH
TTTTHTHHH
TTTTTTTTT

HHHTTTHHH
HHHTHTTTT
TTTTTTTTT

-----------bfs-----------
HHHTTTHHH
TTTTHTHHH
TTTTTTTTT

HHHTTTHHH
HHHTHTTTT
TTTTTTTTT