using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace z45
{
    public partial class Form1 : Form
    {
        int width, height;
        string filename;
        string bestPath;
        int step;
        string[] maze;
        RichTextBox a;

        void load()
        {
            string[] a = System.IO.File.ReadAllText(filename).Split('\n');
            string[] b = a[0].Split(' ');
            width = int.Parse(b[0]);
            height = int.Parse(b[1]);
            maze = new string[height];
            for (int i = 0; i < height; i++)
            {
                maze[i] = a[i + 1];
            }
        }

        string l(string a)
        {
            return a == "" ? "" : a[a.Length - 1].ToString();
        }

        void findPath(string path, int x, int y, char move, bool[][] visited)
        {
            switch (move)
            {
                case 'v':
                    x++;
                    break;
                case '^':
                    x--;
                    break;
                case '>':
                    y++;
                    break;
                case '<':
                    y--;
                    break;
            }
            path += move;

            if (x < 0 || y < 0) return;
            if (x >= height || y >= width) return;
            if (maze[x][y] == 'X') return;
            if (visited[x][y]) return;
            if (maze[x][y] == '#')
            {
                foundPath(path);
                return;
            }
            visited[x][y] = true;

            runAll(path, x, y, visited);
        }

        void runAll(string path, int x, int y, bool[][] input)
        {
            findPath(path, x, y, 'v', input);
            findPath(path, x, y, '^', input);
            findPath(path, x, y, '<', input);
            findPath(path, x, y, '>', input);
        }

        void foundPath(string path)
        {
            MessageBox.Show("Found a path!");
            if (bestPath == "" || path.Length < bestPath.Length)
                bestPath = path;
        }

        string findPath(int mode)
        {
            int wX = -1, wY = -1;
            for(int x = 0; x < height; x++)
                for(int y = 0; y < width; y++)
                    if (maze[x][y] == '&')
                    {
                        wX = x;
                        wY = y;
                    }
            if (wX == -1)
            {
                MessageBox.Show("V bludišti není bílá paní!", "Vyskytla se chyba", MessageBoxButtons.OK, MessageBoxIcon.Error);
                return "";
            }
            bool[][] blank = new bool[height][];
            for(int i = 0; i < height; i++) blank[i] = new bool[width];
            bestPath = "";
            
            runAll("", wX, wY, blank);

            return bestPath;
        }

        public Form1()
        {
            InitializeComponent();
            OpenFileDialog o = new OpenFileDialog();
            o.CheckFileExists = true;
            o.CheckPathExists = true;
            o.Title = "Vyberte soubor s bludištěm...";
            o.ShowDialog();
            filename = o.FileName;
            load();
            string mz_ = "";
            foreach (string s in maze)
                mz_ += s + "\n";
            mz_ = mz_.TrimEnd('\n');
            a = new RichTextBox();
            a.Location = new Point(5, 25);
            a.BackColor = Color.White;
            a.ForeColor = Color.Black;
            a.BorderStyle = BorderStyle.FixedSingle;
            a.WordWrap = false;
            a.ReadOnly = true;
            a.Text = mz_;
            a.Font = new Font("Courier New", 12, FontStyle.Bold);
            this.Controls.Add(a);
            this.Size = new Size(500, 500);
            this.CenterToScreen();
            Form1_Resize("", EventArgs.Empty);
            MenuStrip ms = new MenuStrip();
            ms.Location = new Point(0, 0);
            ms.Dock = DockStyle.Top;
            ms.Size = new Size(580, 50);
            ms.Name = "ms";
            ms.Text = "ms";
            ms.Show();
            this.MainMenuStrip = ms;
            this.Controls.Add(ms);
            ToolStripMenuItem find = new ToolStripMenuItem("Najít cestu");
            find.Click += new EventHandler(find_Click);
            ms.Items.Add(find);
            this.Resize += new EventHandler(Form1_Resize);
        }

        void Form1_Resize(object sender, EventArgs e)
        {
            a.Width = this.Width - 30;
            a.Height = this.Height - 70;
        }

        void find_Click(object sender, EventArgs e)
        {
            findPath(0);
            step = bestPath.Length;
            this.MainMenuStrip.Items.Clear();
            ToolStripMenuItem back = new ToolStripMenuItem("Zpět");
            ToolStripMenuItem forward = new ToolStripMenuItem("Vpřed");
            ToolStripMenuItem steps = new ToolStripMenuItem("Krok: " + step + ".");
            steps.Name = "steps";
            back.Click += new EventHandler(back_Click);
            forward.Click += new EventHandler(forward_Click);
            steps.Enabled = false;
            this.MainMenuStrip.Items.Add(back);
            this.MainMenuStrip.Items.Add(forward);
            this.MainMenuStrip.Items.Add(steps);
            drawSteps(step);
        }

        string[] change(string[] input, int x, int y, char newVal)
        {
            string[] r = new string[input.Length];
            for (int i = 0; i < height; i++)
            {
                for (int j = 0; j < width; j++)
                {
                    if (i == x && j == y)
                        r[i] += newVal;
                    else
                        r[i] += input[i][j];
                }
            }
            return r;
        }

        void drawSteps(int steps)
        {
            int x = -1, y = -1;
            for (int i = 0; i < height; i++)
                for (int j = 0; j < width; j++)
                    if (maze[i][j] == '&')
                    {
                        x = i;
                        y = j;
                    }
            string[] mz = maze;
            if (x != -1)
            {
                for (int i = 0; i < steps; i++)
                {
                    mz = change(mz, x, y, bestPath[i]);
                    switch (bestPath[i])
                    {
                        case 'v':
                            x++;
                            break;
                        case '^':
                            x--;
                            break;
                        case '>':
                            y++;
                            break;
                        case '<':
                            y--;
                            break;
                    }
                }
            }
            string r = "";
            foreach (string s in mz)
                r += s + "\n";
            a.Text = r;
        }

        void forward_Click(object sender, EventArgs e)
        {
            if (step < bestPath.Length) step++;
            this.MainMenuStrip.Items["steps"].Text = "Krok: " + step + ".";
            drawSteps(step);
        }

        void back_Click(object sender, EventArgs e)
        {
            if (step > 0) step--;
            this.MainMenuStrip.Items["steps"].Text = "Krok: " + step + ".";
            drawSteps(step);
        }
    }
}