using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Media;
using Microsoft.Xna.Framework.Net;
using Microsoft.Xna.Framework.Storage;


namespace MoveCostTest01
{
    /// <summary>
    /// This is the main type for your game
    /// </summary>
    public class Game1 : Microsoft.Xna.Framework.Game
    {
        GraphicsDeviceManager graphics;
        SpriteBatch spriteBatch;


        private const int INF = 1000000000;
        private const int vMax = 16;


        int n;
        int[,] dist;
        int[] cost;
        bool[] used;



        public Game1()
        {
            graphics = new GraphicsDeviceManager(this);
            Content.RootDirectory = "Content";
        }

        /// <summary>
        /// Allows the game to perform any initialization it needs to before starting to run.
        /// This is where it can query for any required services and load any non-graphic
        /// related content.  Calling base.Initialize will enumerate through any components
        /// and initialize them as well.
        /// </summary>
        protected override void Initialize()
        {
            // TODO: Add your initialization logic here

            base.Initialize();
        }

        /// <summary>
        /// LoadContent will be called once per game and is the place to load
        /// all of your content.
        /// </summary>
        protected override void LoadContent()
        {
            // Create a new SpriteBatch, which can be used to draw textures.
            spriteBatch = new SpriteBatch(GraphicsDevice);

            // TODO: use this.Content to load your game content here

            // フィールドの移動コストの初期化
            this.dist = new int[,]
            {
                {1, 3, 5, 6, 6, 4, 4, 7, 8, 2, 9, 3, 9, 1, 9, 1},
                {9, 2, 3, 7, 1, 3, 6, 8, 4, 1, 8, 7, 5 ,6, 2, 3},
                {2, 5, 3, 5, 6, 7, 2, 1, 3, 4, 5, 2, 8, 4, 7, 8},
                {3, 5, 4, 2, 3, 4, 6, 1, 3, 6, 6, 4, 5, 6, 2, 3},
                {1, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
                {1, 5, 3, 1, 9, 5, 3, 5, 7, 4, 8, 3, 5, 9, 5, 9},
                {1, 9, 8, 4, 7, 9, 4, 9, 8, 3, 7, 6, 7, 9, 7, 1},
                {4, 1, 8, 1, 7, 1, 5, 8, 3, 1, 4, 5, 9, 3, 5, 7},
                {7, 5, 9, 1, 3, 9, 5, 9, 3, 9, 1, 5, 8, 3, 7, 5},
                {1, 6, 3, 2, 1, 9, 8, 8, 9, 1, 5, 7, 8, 1, 5, 1},
                {8, 3, 5, 5, 9, 1, 7, 5, 5, 6, 1, 5, 1, 7, 4, 9},
                {8, 9, 9, 9, 3, 6, 1, 3, 4, 5, 9, 4, 5, 7, 5, 6},
                {8, 4, 9, 4, 9, 7, 5, 7, 5, 4, 4, 7, 3, 5, 7, 4},
                {4, 3, 9, 7, 5, 6, 1, 6, 3, 3, 4, 9, 3, 5, 7, 3},
                {5, 1, 3, 5, 5, 9, 1, 6, 9, 4, 8, 9, 9, 5, 4, 7},
                {9, 5, 5, 8, 5, 6, 4, 6, 4, 6, 1, 4, 4, 9, 5, 2},
            };

            this.cost = new int[this.dist.GetLength(0)];
            this.used = new bool[this.dist.GetLength(0)];


            n = 16;
            int goal = 3;
            this.dijkstra(goal);
            this.consoleOut();
            Console.WriteLine(this.n.ToString());
        }

        /// <summary>
        /// UnloadContent will be called once per game and is the place to unload
        /// all content.
        /// </summary>
        protected override void UnloadContent()
        {
            // TODO: Unload any non ContentManager content here
        }

        /// <summary>
        /// Allows the game to run logic such as updating the world,
        /// checking for collisions, gathering input, and playing audio.
        /// </summary>
        /// <param name="gameTime">Provides a snapshot of timing values.</param>
        protected override void Update(GameTime gameTime)
        {
            // Allows the game to exit
            if (GamePad.GetState(PlayerIndex.One).Buttons.Back == ButtonState.Pressed)
                this.Exit();

            // TODO: Add your update logic here

            base.Update(gameTime);
        }

        /// <summary>
        /// This is called when the game should draw itself.
        /// </summary>
        /// <param name="gameTime">Provides a snapshot of timing values.</param>
        protected override void Draw(GameTime gameTime)
        {
            GraphicsDevice.Clear(Color.CornflowerBlue);

            // TODO: Add your drawing code here

            base.Draw(gameTime);
        }


        // ダイクストラ法による最短経路探索
        private void dijkstra(int goal)
        {
            int x, y, min;
            for (x = 0; x < n; x++)
            {
                this.cost[x] = INF;
                this.used[x] = false;
            }
            this.cost[goal] = 0;
            while (true)
            {
                min = INF;
                for (x = 0; x < n; x++)
                {
                    if (this.used[x] && min > this.cost[x])
                        min = this.cost[x];
                }
                if (min == INF)
                    break;
                for (y = 0; y < n; y++)
                {
                    if (this.cost[y] == min)
                    {
                        for (x = 0; x < n; x++)
                        {
                            if (this.cost[x] > this.dist[x, y] + this.cost[y])
                                this.cost[x] = this.dist[x, y] + this.cost[y];
                        }
                    }
                }
            }
        }


        private void consoleOut()
        {
            for (int i = 0; i < this.used.Length; i++)
            {
                Console.WriteLine(
                    "i = " + i.ToString()
                    + "\tused = " + this.used[i].ToString()
                    + "\tcost = " + this.cost[i].ToString());
            }

        }
    }
}