using System;
using System.Collections.Generic;
using Com.CodeGame.CodeRacing2015.DevKit.CSharpCgdk.Model;


public class WayFinder
{
    public List<Tile> way;
    private TileType[][] map;
    public int[][] isMached;

    private bool rematch;

    public int[] startPos;

    public int[] targetPos;

    public WayFinder()
    {
        this.map = null;
        this.startPos = new int[2] {0,0};
        this.targetPos = new int[2] { 0, 0 };
        rematch = false;
    }

    public WayFinder(TileType[][] map)
    {

        SetMap(map);
        this.startPos = new int[2] { 0, 0 };
        this.targetPos = new int[2] { 0, 0 };
        rematch = true;
    }


    public void SetMap(TileType[][] map)
    {
        this.map = map;

    }

    private int BLANK = -2;
    private int EMPTY = -1;
    private int len = 0;

    private bool isCome(int x, int y, int dx, int dy)
    {
        TileType t1 = map[x][y];
       // TileType t2 = map[x+dx][y+dy];

        if(dx > 0)
        {
            switch (t1)
            {
                case TileType.Vertical:
                case TileType.RightTopCorner:
                case TileType.RightBottomCorner:
                case TileType.LeftHeadedT:
                    return false;
            }

            return true;
        }

        if (dx < 0)
        {
            switch (t1)
            {
                case TileType.Vertical:
                case TileType.LeftTopCorner:
                case TileType.LeftBottomCorner:
                case TileType.RightHeadedT:
                    return false;
            }

            return true;
        }

        if (dy < 0)
        {
            switch (t1)
            {
                case TileType.Horizontal:
                case TileType.LeftTopCorner:
                case TileType.RightTopCorner:
                case TileType.BottomHeadedT:
                    return false;
            }
            return true;
        }

        if (dy > 0)
        {
            switch (t1)
            {
                case TileType.Horizontal:
                case TileType.LeftBottomCorner:
                case TileType.RightBottomCorner:
                case TileType.TopHeadedT:
                    return false;
            }

            return true;
        }



        return true;
    }

    public bool MathPath()
    {
        ClearIsMached();
        if (way != null)
            way.Clear();
        else
            way = new List<Tile>();

        int[] dx = new int[4] { -1, 0, 1, 0 };
        int[] dy = new int[4] { 0, 1, 0, -1 };
        int d, x, y, k;

        int W = map.Length;
        int H = map[0].Length;

        int ax = startPos[0];
        int ay = startPos[1];

        int bx = targetPos[0];
        int by = targetPos[1];


        bool stop;

        if (isMached[ax][ay] == EMPTY || isMached[bx][by] == EMPTY) return false;  // ячейка (ax, ay) или (bx, by) - стена

        // распространение волны
        d = 0;
        isMached[ax][ay] = 0;            // стартовая ячейка помечена 0
        do
        {
            stop = true;               // предполагаем, что все свободные клетки уже помечены
            for (y = 0; y < H; ++y)
                for (x = 0; x < W; ++x)
                    if (isMached[x][y] == d)                         // ячейка (x, y) помечена числом d
                    {
                        for (k = 0; k < 4; ++k)                    // проходим по всем непомеченным соседям
                        {
                            if (isCome(x, y, dx[k], dy[k])) {

                                int iy = y + dy[k], ix = x + dx[k];
                                if (iy >= 0 && iy < H && ix >= 0 && ix < W &&
                                     isMached[ix][iy] == BLANK)
                                {
                                    stop = false;              // найдены непомеченные клетки
                                    isMached[ix][iy] = d + 1;      // распространяем волну
                                }
                            }
                        }
                    }
            d++;
        } while (!stop && isMached[bx][by] == BLANK);

        if (isMached[bx][by] == BLANK) return false;  // путь не найден

        // восстановление пути

        len = isMached[bx][by];            // длина кратчайшего пути из (ax, ay) в (bx, by)
        x = bx;
        y = by;
        d = len;

        while (d > 0)
        {
            Tile tile = new Tile();
            tile.type = map[x][y];
            tile.x = x;
            tile.y = y;
            way.Add(tile);

            //px[d] = x;
            //py[d] = y;                   // записываем ячейку (x, y) в путь
            d--;
            for (k = 0; k < 4; ++k)
            {
                int iy = y + dy[k], ix = x + dx[k];
                if (iy >= 0 && iy < H && ix >= 0 && ix < W &&
                     isMached[ix][iy] == d)
                {
                    x = x + dx[k];
                    y = y + dy[k];           // переходим в ячейку, которая на 1 ближе к старту
                    break;
                }
            }
        }
        /*
        Tile t = new Tile();
        t.type = map[bx][by];
        t.x = bx;
        t.y = by;
        way.Insert(0,t);
        */
        //px[0] = ax;
        //py[0] = ay;                    // теперь px[0..len] и py[0..len] - координаты ячеек пути
        return true;
    }

    private void ClearIsMached()
    {
        if (isMached != null)
        {
            for (int i = 0; i < isMached.Length; i++)
                for (int j = 0; j < isMached[i].Length; j++)
                {
                    int t = -2;
                    if (map[i][j] == TileType.Empty || map[i][j] == TileType.Unknown)
                        t = -1;
                    isMached[i][j] = t;
                }
        }
        else
        {
            isMached = new int[map.Length][];
            for (int i = 0; i < isMached.Length; i++)
                isMached[i] = new int[map[0].Length];

            ClearIsMached();
        }
    }
}
    public class Tile
    {
        public int x;
        public int y;

        public Vector wpos;

        public TileType type;

        public Tile()
        {
            wpos = new Vector();
            type = TileType.Unknown;
            x = 0;
            y = 0;
        }
    public override string ToString()
    {
        return string.Format("pos:{0};{1}| type:{2}", x, y, type.ToString());
    }
}