2020-02-26

package com.company;

import java.awt.*;

public class Main {
    private static boolean[][] visited = new boolean[5][4];
    private static int[][] G = {{0, 0, 1, 0},
            {0, 0, 0, 0},
            {0, 0, 1, 0},
            {0, 1, 0, 0},
            {0, 0, 0, 1}};
    private static Point[] direction = {new Point(-1,0),new Point(1,0),new Point(0,1),new Point(0,-1)};
    // 映射装换
    public static Point toXY(int w) {
        Point point = new Point();
        point.x = (w - 1) / 4;
        point.y = (w - 1) % 4;
        return point;
    }

    public static int toPoint(Point point){
        return point.x * 4 + (point.y + 1);
    }

    public static void dfs(int[][] G, int v) {
        Point point = toXY(v);
        visited[point.x][point.y] = true;
        System.out.println(v);
        for (int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
            if (inRange(toXY(w)) && !visited[toXY(w).x][toXY(w).y]) {
                dfs(G, w);
            }
        }
    }

    private static int NextAdjVex(int[][] g, int v, int w) {
        Point wPoint = toXY(w);
        Point vPoint = toXY(v);
        Point dPoint = new Point((wPoint.x - vPoint.x) , (wPoint.y - vPoint.y));
        int index = 0;
        for (int i = 0; i < direction.length; i++) {
            if(direction[i].x == dPoint.x && direction[i].y == dPoint.y){
                index =  i + 1;
                if (index == 3){
                    return 0;
                } else {
                    for (int j = index; j < 3; j++) {
                        Point nextPoint = new Point((vPoint.x + direction[j].x) , vPoint.y + direction[j].y);
                        if (inRange(nextPoint) && !visited[nextPoint.x][nextPoint.y] && g[nextPoint.x][nextPoint.y] != 1){
                            toPoint(nextPoint);
                        }
                    }
                }
                break;
            }
        }
        return 0;
    }

    private static int FirstAdjVex ( int[][] g, int v){
        Point point = toXY(v);
        for (int i = 0; i < direction.length; i++) {
            int x = point.x + direction[i].x;
            int y = point.y + direction[i].y;
            Point newPoint = new Point(x,y);
            if (inRange(newPoint) && !visited[newPoint.x][newPoint.y] && g[newPoint.x][newPoint.y] != 1){
                return toPoint(newPoint);
            }
        }
        return 0;
    }

    private static boolean inRange(Point point) {
        return point.x <= 4 && point.x >=0 && point.y <=3 && point.y >= 0;
    }

    public static void main (String[]args){
        dfs(G,1);
        // write your code here
//        System.out.println(toXY(9));;
//        System.out.println(toXY(10));;
//        System.out.println(toXY(1));;
//        System.out.println(toXY(20));;
    }
}

class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode(int x) { val = x; }
}