微信小程序：一起玩連線，一個算法來搞定

微信小程序：一起玩連線

游戲玩法

　　將相同顏色的結點連接在一起，連線之間不能交叉。

　　

?

算法思想

　　轉換為多個源點到達對應終點的路徑問題，且路徑之間不相交。按照dfs方式尋找兩個結點路徑，一條路徑探索完之后，標記地圖并記錄路徑，然后探索下一條路徑，以此類推。路徑探索失敗之后，地圖進行標記回退，路徑也回退。

import com.sun.org.apache.xml.internal.serialize.LineSeparator;
import java.util.*;
import java.util.stream.IntStream;/*** @author hujunzheng* @create 2018-07-01 16:12**/
public class LineTogether {private static final int[][] dir = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};private boolean[][] map;private List<TogetherNode> togetherNodes;public LineTogether() {Scanner scanner = new Scanner(System.in);int width = scanner.nextInt();int height = scanner.nextInt();int pairNodes = scanner.nextInt();this.map = new boolean[width + 2][];for (int i = 0; i < width + 2; ++i) {map[i] = new boolean[height + 2];}for (int i = 1; i <= width; ++i) {for (int j = 1; j <= height; ++j) {map[i][j] = true;}}togetherNodes = new ArrayList<>();IntStream.range(0, pairNodes).forEach(i -> {int bx = scanner.nextInt();int by = scanner.nextInt();map[bx][by] = false;Node begin = new Node(bx, by);int ex = scanner.nextInt();int ey = scanner.nextInt();map[ex][ey] = false;Node end = new Node(ex, ey);togetherNodes.add(new TogetherNode(begin, end));});this.printMap();}public void resolve() {if (this.togetherNodes.size() == 0) {return;}Node begin = togetherNodes.get(0).begin;Node end = togetherNodes.get(0).end;boolean success = this.process(0, begin.x, begin.y, end.x, end.y);System.out.println(success ? "路徑探測成功" : "路徑探測失敗");}private void printMap() {StringBuilder result = new StringBuilder();for (int i = 0; i < map.length; ++i) {for (int j = 0; j < map[i].length; ++j) {result.append(map[i][j] ? 1 : 0).append(" ");}result.append(LineSeparator.Windows);}System.out.println(result.toString());}private boolean process(int ix, int bx, int by, int ex, int ey) {//如果 map[bx][by] == false, 說明是端點boolean endpoint = !map[bx][by];map[bx][by] = false;List<Node> path = togetherNodes.get(ix).path;path.add(new Node(bx, by));//到達終點if (bx == ex && by == ey) {if (ix + 1 >= togetherNodes.size()) {return true;}Node begin = togetherNodes.get(ix + 1).begin;Node end = togetherNodes.get(ix + 1).end;//下一個路徑探索boolean success = this.process(ix + 1, begin.x, begin.y, end.x, end.y);if (success) return success;} else {for (int i = 0; i < dir.length; ++i) {int nextx = bx + dir[i][0];int nexty = by + dir[i][1];//如果節點標記為false，并且節點不是終節點的時候if (!map[nextx][nexty] && !(nextx == ex && nexty == ey)) {continue;}boolean success = this.process(ix, nextx, nexty, ex, ey);if (success) return true;}}if (!endpoint) {map[bx][by] = true;}path.remove(path.size() - 1);return false;}public String fetchResult() {if (togetherNodes.size() == 0) {return "";}StringBuilder result = new StringBuilder();togetherNodes.stream().map(TogetherNode::getPath).forEach(path -> {for (Iterator<Node> it = path.iterator(); it.hasNext(); ) {Node node = it.next();result.append("(").append(node.x).append(":").append(node.y).append(")");if (it.hasNext()) {result.append("->");}}result.append(LineSeparator.Windows);});return result.toString();}private class Node {public int x;public int y;public Node(int x, int y) {this.x = x;this.y = y;}}private class TogetherNode {public Node begin;public Node end;private List<Node> path;public TogetherNode(Node begin, Node end) {this.begin = begin;this.end = end;path = new ArrayList<>();}public List<Node> getPath() {return path;}}public static void main(String[] args) {LineTogether lt = new LineTogether();lt.resolve();System.out.println(lt.fetchResult());}
}

輸入數據

5 5 5
3 1 1 4
4 1 4 5
4 2 2 3
4 4 5 5
1 5 2 4

輸出數據

路徑探測成功
(3:1)->(2:1)->(1:1)->(1:2)->(1:3)->(1:4)
(4:1)->(5:1)->(5:2)->(5:3)->(4:3)->(3:3)->(3:4)->(3:5)->(4:5)
(4:2)->(3:2)->(2:2)->(2:3)
(4:4)->(5:4)->(5:5)
(1:5)->(2:5)->(2:4)

操作效果

　　

?