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

public class Map {
    private static Random random;

    private int[][] map;
    private int height;
    private int width;

    static {
        random = new Random();
    }

    Map(int height, int width) {
        this.height = height;
        this.width = width;
        this.map = new int[height][width];
    }

    public void printMap() {
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                //System.out.printf("%d\t", map[i][j]);
                if (map[i][j] == -1)
                    System.out.print(" " + map[i][j]);
                else
                    System.out.print("  " + map[i][j]);
            }
            System.out.println();
        }
    }

    public void randMap() {
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (random.nextInt(6) == 0)
                    map[i][j] = -1;
                else
                    map[i][j] = 0;
            }
        }
    }

    public void findPath(int x1, int y1, int x2, int y2) {
        map[x2][y2] = 0;
        int key = 1;
        map[x1][y1] = 1;
        boolean find;
        do {
            find = false;
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    if (map[i][j] == key) {
                        if (i > 0 && map[i - 1][j] == 0) {
                            map[i - 1][j] = key + 1;
                            find = true;
                        }
                        if (j < width - 1 && map[i][j + 1] == 0) {
                            map[i][j + 1] = key + 1;
                            find = true;
                        }
                        if (i < height - 1 && map[i + 1][j] == 0) {
                            map[i + 1][j] = key + 1;
                            find = true;
                        }
                        if (j > 0 && map[i][j - 1] == 0) {
                            map[i][j - 1] = key + 1;
                            find = true;
                        }
                    }
                }
            }
            key++;
        } while (find);


        int[][] road = new int[width - 1][height - 1];
        key = map[x2][y2];
        int keyCopy = key;
        for (int i = key; i >= 0; i--) {
            keyCopy--;
            if (x2 != width - 1 && y2 != height - 1) {
                if (map[x2][y2 - 1] == keyCopy) {
                    y2--;
                    road[x2][y2] = keyCopy;
                } else {
                    if (map[x2 - 1][y2] == keyCopy) {
                        x2--;
                        road[x2][y2] = keyCopy;
                    } else {
                        if (map[x2][y2 + 1] == keyCopy) {
                            y2--;
                            road[x2][y2] = keyCopy;
                        } else {
                            if (map[x2 + 1][y2] == keyCopy) {
                                x2++;
                                road[x2][y2] = keyCopy;
                            }
                        }
                    }
                }
            }
            if (x2 == width - 1 && y2 != height - 1) {
                if (map[x2][y2 - 1] == keyCopy) {
                    y2--;
                    road[x2][y2] = keyCopy;
                } else {
                    if (map[x2 - 1][y2] == keyCopy) {
                        x2--;
                        road[x2][y2] = keyCopy;
                    } else {
                        if (map[x2][y2 + 1] == keyCopy) {
                            y2++;
                            road[x2][y2] = keyCopy;
                        }
                    }
                }
            }
            if (x2 != width - 1 && y2 == height - 1) {
                if (map[x2 + 1][y2] == keyCopy) {
                    x2++;
                    road[x2][y2] = keyCopy;
                } else {
                    if (map[x2][y2 - 1] == keyCopy) {
                        y2--;
                        road[x2][y2] = keyCopy;
                    } else {
                        if (map[x2 - 1][y2] == keyCopy) {
                            x2--;
                            road[x2][y2] = keyCopy;
                        }
                    }
                }
            }
            if (x2 == width - 1 && y2 == height - 1) {
                if (map[x2][y2 - 1] == keyCopy) {
                    y2--;
                    road[x2][y2] = keyCopy;
                } else {
                    if (map[x2 - 1][y2] == keyCopy) {
                        x2--;
                        road[x2][y2] = keyCopy;
                    }
                }
            }
        }

        for (int i = 0; i < width; i++)
            for (int j = 0; j < height; j++)
                if (map[i][j] != -1) map[i][j] = 0;

        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++){
                if (map[i][j] != -1)
                    map[i][j] = road[i][j];
            }
        }

    }
}