using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApp1
{
    class Program
    {
        static void Main()
        {
            int[][] matrix = new int[][] {
                new int[] { 0, 0, 0, 0, 5, 0, 0, 0, 0, 5, 0, 0, 0, 5},
                new int[] { 1, 9, 9, 9, 1, 1, 9, 9, 9, 1, 1, 9, 9, 1},
                new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                new int[] { 2, 9, 9, 9, 2, 2, 9, 9, 9, 2, 2, 9, 9, 2},
                new int[] { 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0},
                new int[] { 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 8}
            };

            int[][] queries = new int[][] {
                new int[]{ 0, 0, 6, 13}
            };
            int[] result = shortestPath(matrix, queries);
            Console.WriteLine();
        }
        static int[] shortestPath(int[][] a, int[][] queries)
        {
            int[] result = new int[queries.Length];
            Node[][] tempGoldenPath = new Node[a.Length][];
            Node[][] goldenPath = new Node[a.Length][];
            for (int i = 0; i < goldenPath.Length; i++)
            {
                tempGoldenPath[i] = new Node[a[0].Length];
                goldenPath[i] = new Node[a[0].Length];
            }
            TraverseBestPath(a, a.Length / 2, a.Length / 2, 0, a[0].Length - 1, tempGoldenPath, true, goldenPath);
            Node startingNode = new Node(a[a.Length / 2][0], a.Length / 2, 0);
            Node currentNode = tempGoldenPath[a.Length / 2][a[0].Length - 1];
            goldenPath[a.Length / 2][a[0].Length - 1] = new Node(tempGoldenPath[a.Length / 2][a[0].Length - 1].value, a.Length / 2, a[0].Length - 1);
            goldenPath[a.Length / 2][0] = new Node(a[a.Length / 2][0], a.Length / 2, 0);
            while (currentNode.row != startingNode.row || currentNode.col != startingNode.col)
            {
                goldenPath[currentNode.parentRow][currentNode.parentCol] = new Node(a[currentNode.parentRow][currentNode.parentCol], currentNode.parentRow, currentNode.parentCol);
                currentNode = tempGoldenPath[currentNode.parentRow][currentNode.parentCol];
            }

            /*for (int i = 0; i < a.Length; i++)
            {
                for (int j = 0; j < a[0].Length; j++)
                {
                    Console.Write(goldenPath[i][j] == null ? "n" : goldenPath[i][j].value + "");
                }
                Console.WriteLine();
            }*/

            for (int i = 0; i < queries.Length; i++)
            {
                Node[][] paths = new Node[a.Length][];
                for (int j = 0; j < paths.Length; j++) paths[j] = new Node[a[0].Length];
                result[i] = TraverseBestPath(a, queries[i][0], queries[i][2], queries[i][1], queries[i][3], paths, false, goldenPath);
            }
            return result;
        }

        static int TraverseBestPath(int[][] a, int startRow, int endRow, int startCol, int endCol, Node[][] paths, bool initialTraverse, Node[][] goldenPath)
        {
            if (startRow == endRow && startCol == endCol) return a[startRow][startCol];
            PriorityQueue queue = new PriorityQueue();
            Node startNode = new Node(a[startRow][startCol], startRow, startCol);
            queue.Enqueue(startNode);
            Node endNode = new Node(int.MaxValue, endRow, endCol);
            endNode.isFinish = true;
            paths[endRow][endCol] = endNode;
            while (queue.Count() > 0)
            {
                if (queue.Peek().value > endNode.value) break;
                Node node = queue.Dequeue();
                if (node.isVisited) continue;
                node.isVisited = true;
                paths[node.row][node.col] = node;
                if (initialTraverse == false)
                {
                    if (goldenPath[node.row][node.col] != null)
                    {
                        if (queue.Peek() == null || queue.Peek().value > node.value)
                        {
                            int rowStartGoldenPath = node.row;
                            int colStartGoldenPath = node.col;
                            int value = node.value;
                            PriorityQueue queueReverse = new PriorityQueue();
                            Node startNodeReverse = new Node(a[endRow][endCol], endRow, endCol);
                            Node endNodeReverse = new Node(int.MaxValue, startRow, startCol);
                            paths[startRow][startCol] = endNodeReverse;
                            queueReverse.Enqueue(startNodeReverse);
                            while (queueReverse.Count() > 0)
                            {
                                if (queueReverse.Peek().value > endNodeReverse.value) break;
                                Node nodeReverse = queueReverse.Dequeue();
                                if (nodeReverse.isVisited) continue;
                                nodeReverse.isVisited = true;

                                if (goldenPath[nodeReverse.row][nodeReverse.col] != null && queueReverse.Peek().value > nodeReverse.value)
                                {
                                    int result = value + nodeReverse.value;
                                    while (rowStartGoldenPath != nodeReverse.row || colStartGoldenPath != nodeReverse.col)
                                    {
                                        nodeReverse = goldenPath[nodeReverse.parentRow][nodeReverse.parentCol];
                                        result += nodeReverse.value;
                                    }
                                    return result;
                                }
                                if (nodeReverse.row > 0) PopulatePaths(a, paths, queueReverse, nodeReverse, -1, 0);
                                if (nodeReverse.row < paths.Length - 1) PopulatePaths(a, paths, queueReverse, nodeReverse, +1, 0);
                                if (nodeReverse.col > 0) PopulatePaths(a, paths, queueReverse, nodeReverse, 0, -1);
                                if (nodeReverse.col < paths[0].Length - 1) PopulatePaths(a, paths, queueReverse, nodeReverse, 0, +1);
                                paths[nodeReverse.row][nodeReverse.col] = nodeReverse;
                            }
                            return endNodeReverse.value;
                        }
                    }
                }
                if (node.row > 0) PopulatePaths(a, paths, queue, node, -1, 0);
                if (node.row < paths.Length - 1) PopulatePaths(a, paths, queue, node, +1, 0);
                if (node.col > 0) PopulatePaths(a, paths, queue, node, 0, -1);
                if (node.col < paths[0].Length - 1) PopulatePaths(a, paths, queue, node, 0, +1);
            }
            return endNode.value;
        }

        static void PopulatePaths(int[][] a, Node[][] paths, PriorityQueue queue, Node node, int row, int col)
        {
            if (paths[node.row + row][node.col + col] == null)
            {
                paths[node.row + row][node.col + col] = new Node(node.value + a[node.row + row][node.col + col], node.row + row, node.col + col);
                paths[node.row + row][node.col + col].parentRow = node.row;
                paths[node.row + row][node.col + col].parentCol = node.col;
                queue.Enqueue(paths[node.row + row][node.col + col]);
            }
            else
            {
                if (paths[node.row + row][node.col + col].isFinish == true)
                {
                    if (paths[node.row + row][node.col + col].value > paths[node.row][node.col].value + a[node.row + row][node.col + col])
                    {
                        paths[node.row + row][node.col + col].value = paths[node.row][node.col].value + a[node.row + row][node.col + col];
                        paths[node.row + row][node.col + col].parentRow = node.row;
                        paths[node.row + row][node.col + col].parentCol = node.col;
                    }
                }
            }
        }

        public class Node
        {
            public int value;
            public int row;
            public int col;
            public bool isVisited;
            public bool isFinish;
            public int parentRow;
            public int parentCol;

            public Node(int value, int row, int col)
            {
                this.value = value;
                this.row = row;
                this.col = col;
                this.parentRow = -1;
                this.parentCol = -1;
            }
        }

        public class PriorityQueue
        {
            private List<Node> data;

            public PriorityQueue()
            {
                this.data = new List<Node>();
            }

            public void Enqueue(Node item)
            {
                data.Add(item);
                int ci = data.Count - 1;
                while (ci > 0)
                {
                    int pi = (ci - 1) / 2;
                    if (data[ci].value.CompareTo(data[pi].value) >= 0) break;
                    Node tmp = data[ci]; data[ci] = data[pi]; data[pi] = tmp;
                    ci = pi;
                }
            }

            public Node Dequeue()
            {
                int li = data.Count - 1;
                Node frontItem = data[0];
                data[0] = data[li];
                data.RemoveAt(li);

                --li;
                int pi = 0;
                while (true)
                {
                    int ci = pi * 2 + 1;
                    if (ci > li) break;
                    int rc = ci + 1;
                    if (rc <= li && data[rc].value.CompareTo(data[ci].value) < 0)
                        ci = rc;
                    if (data[pi].value.CompareTo(data[ci].value) <= 0) break;
                    Node tmp = data[pi]; data[pi] = data[ci]; data[ci] = tmp;
                    pi = ci;
                }
                return frontItem;
            }

            public Node Peek()
            {
                return data.Count() > 0 && data[0] != null ? data[0] : null;
            }

            public int Count()
            {
                return data.Count;
            }

            public bool IsConsistent()
            {
                if (data.Count == 0) return true;
                int li = data.Count - 1;
                for (int pi = 0; pi < data.Count; ++pi)
                {
                    int lci = 2 * pi + 1;
                    int rci = 2 * pi + 2;

                    if (lci <= li && data[pi].value.CompareTo(data[lci].value) > 0) return false;
                    if (rci <= li && data[pi].value.CompareTo(data[rci].value) > 0) return false;
                }
                return true;
            }
        } // Priority
    }
}