/*
    Copyright (c) 1998 Anarchriz. All rights reserved. You may copy portions
    of code if you credit me.
    
    TO-DO: comment the stuff
*/

import java.awt.*;

public class Maze
{

    public Maze(byte maze[][], int M, int N)
    {
        this.M = 6;
        this.N = 7;
        shortestPath = 0x7fffffff;
        numberOfCoordinates = 1;
        ready = false;
        this.maze = maze;
        this.M = M;
        this.N = N;
        mazeCounter = new int[M][N];
        coArray = new int[M * N][2];
        mazeCounter[0][0] = 0x7fffffff;
    }

    public void solve()
    {
        ready = false;
        do
        {
            lengthPath++;
            nextNumberOfCoordinates = 0;
            for(int i = 0; i < numberOfCoordinates; i++)
            {
                int row = coArray[i][0];
                int column = coArray[i][1];
                coArray[i][0] = 0;
                coArray[i][1] = 0;
                if(isZero(row, column + 1))
                    addCoordinate(row, column + 1);
                if(ready)
                    break;
                if(isZero(row + 1, column))
                    addCoordinate(row + 1, column);
                if(ready)
                    break;
                if(isZero(row, column - 1))
                    addCoordinate(row, column - 1);
                if(ready)
                    break;
                if(isZero(row - 1, column))
                    addCoordinate(row - 1, column);
                if(ready)
                    break;
            }

            numberOfCoordinates = nextNumberOfCoordinates;
            if(numberOfCoordinates == 0)
                ready = true;
            if(!ready)
                wipeCoArrayClean();
        }
        while(!ready);
    }

    private void addCoordinate(int row, int column)
    {
        int pos = findPos();
        coArray[pos][0] = row;
        coArray[pos][1] = column;
        mazeCounter[row][column] = lengthPath;
        nextNumberOfCoordinates++;
        if(row == M - 1 && column == N - 1)
        {
            ready = true;
            shortestPath = lengthPath;
            tracePad();
        }
    }

    private void wipeCoArrayClean()
    {
        int pos = findPos();
        if(pos >= numberOfCoordinates)
            return;
        for(int i = coArray.length - 1; i >= 0; i--)
        {
            pos = findPos();
            if(pos >= numberOfCoordinates)
                return;
            if(coArray[i][0] != 0 || coArray[i][1] != 0)
            {
                coArray[pos][0] = coArray[i][0];
                coArray[pos][1] = coArray[i][1];
                coArray[i][0] = 0;
                coArray[i][1] = 0;
            }
        }

    }

    private int findPos()
    {
        for(int pos = 0; pos < coArray.length; pos++)
            if(coArray[pos][0] == 0 && coArray[pos][1] == 0)
                return pos;

        return 0x7fffffff;
    }

    private void tracePad()
    {
        int row = M - 1;
        int column = N - 1;
        coArray[lengthPath][0] = row;
        coArray[lengthPath][1] = column;
        mazeCounter[0][0] = 0;
        for(int i = lengthPath - 1; i >= 0; i--)
        {
            if(isThis(row - 1, column, i))
                row--;
            else
            if(isThis(row, column - 1, i))
                column--;
            else
            if(isThis(row + 1, column, i))
                row++;
            else
            if(isThis(row, column + 1, i))
                column++;
            coArray[i][0] = row;
            coArray[i][1] = column;
        }

    }

    private boolean isThis(int row, int column, int value)
    {
        if(row < 0 || row >= M || column < 0 || column >= N)
            return false;
        return mazeCounter[row][column] == value;
    }

    private boolean isZero(int row, int column)
    {
        if(row < 0 || row >= M || column < 0 || column >= N)
            return false;
        return maze[row][column] == 0 && mazeCounter[row][column] == 0;
    }

    public void printMaze(Panel panel, TextField output)
    {
        if(shortestPath == 0x7fffffff)
        {
            output.setText("There is no path.");
            return;
        }
        output.setText("A shortest path is " + shortestPath + " steps!");
        for(int i = 0; i <= shortestPath; i++)
        {
            TextField t = (TextField)panel.getComponent(coArray[i][0] * N + coArray[i][1]);
            t.setBackground(Color.green);
            t.setText("");
        }

    }

    private byte maze[][];
    private int M;
    private int N;
    private int shortestPath;
    private int lengthPath;
    private int mazeCounter[][];
    private int coArray[][];
    private int numberOfCoordinates;
    private int nextNumberOfCoordinates;
    private boolean ready;
}