daily pastebin goal
0%
SHARE
TWEET

Untitled

a guest Mar 23rd, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6. namespace ConsoleApp1
  7. {
  8.     class Program
  9.     {
  10.         static void Main()
  11.         {
  12.             int[][] matrix = new int[][] {
  13.                 new int[] { 0, 0, 0, 0, 5, 0, 0, 0, 0, 5, 0, 0, 0, 5},
  14.                 new int[] { 1, 9, 9, 9, 1, 1, 9, 9, 9, 1, 1, 9, 9, 1},
  15.                 new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  16.                 new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  17.                 new int[] { 2, 9, 9, 9, 2, 2, 9, 9, 9, 2, 2, 9, 9, 2},
  18.                 new int[] { 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0},
  19.                 new int[] { 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 8}
  20.             };
  21.  
  22.             int[][] queries = new int[][] {
  23.                 new int[]{ 0, 0, 6, 13}
  24.             };
  25.             int[] result = shortestPath(matrix, queries);
  26.             Console.WriteLine();
  27.         }
  28.         static int[] shortestPath(int[][] a, int[][] queries)
  29.         {
  30.             int[] result = new int[queries.Length];
  31.             Node[][] tempGoldenPath = new Node[a.Length][];
  32.             Node[][] goldenPath = new Node[a.Length][];
  33.             for (int i = 0; i < goldenPath.Length; i++)
  34.             {
  35.                 tempGoldenPath[i] = new Node[a[0].Length];
  36.                 goldenPath[i] = new Node[a[0].Length];
  37.             }
  38.             TraverseBestPath(a, a.Length / 2, a.Length / 2, 0, a[0].Length - 1, tempGoldenPath, true, goldenPath);
  39.             Node startingNode = new Node(a[a.Length / 2][0], a.Length / 2, 0);
  40.             Node currentNode = tempGoldenPath[a.Length / 2][a[0].Length - 1];
  41.             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);
  42.             goldenPath[a.Length / 2][0] = new Node(a[a.Length / 2][0], a.Length / 2, 0);
  43.             while (currentNode.row != startingNode.row || currentNode.col != startingNode.col)
  44.             {
  45.                 goldenPath[currentNode.parentRow][currentNode.parentCol] = new Node(a[currentNode.parentRow][currentNode.parentCol], currentNode.parentRow, currentNode.parentCol);
  46.                 currentNode = tempGoldenPath[currentNode.parentRow][currentNode.parentCol];
  47.             }
  48.  
  49.             /*for (int i = 0; i < a.Length; i++)
  50.             {
  51.                 for (int j = 0; j < a[0].Length; j++)
  52.                 {
  53.                     Console.Write(goldenPath[i][j] == null ? "n" : goldenPath[i][j].value + "");
  54.                 }
  55.                 Console.WriteLine();
  56.             }*/
  57.  
  58.             for (int i = 0; i < queries.Length; i++)
  59.             {
  60.                 Node[][] paths = new Node[a.Length][];
  61.                 for (int j = 0; j < paths.Length; j++) paths[j] = new Node[a[0].Length];
  62.                 result[i] = TraverseBestPath(a, queries[i][0], queries[i][2], queries[i][1], queries[i][3], paths, false, goldenPath);
  63.             }
  64.             return result;
  65.         }
  66.  
  67.         static int TraverseBestPath(int[][] a, int startRow, int endRow, int startCol, int endCol, Node[][] paths, bool initialTraverse, Node[][] goldenPath)
  68.         {
  69.             if (startRow == endRow && startCol == endCol) return a[startRow][startCol];
  70.             PriorityQueue queue = new PriorityQueue();
  71.             Node startNode = new Node(a[startRow][startCol], startRow, startCol);
  72.             queue.Enqueue(startNode);
  73.             Node endNode = new Node(int.MaxValue, endRow, endCol);
  74.             endNode.isFinish = true;
  75.             paths[endRow][endCol] = endNode;
  76.             while (queue.Count() > 0)
  77.             {
  78.                 if (queue.Peek().value > endNode.value) break;
  79.                 Node node = queue.Dequeue();
  80.                 if (node.isVisited) continue;
  81.                 node.isVisited = true;
  82.                 paths[node.row][node.col] = node;
  83.                 if (initialTraverse == false)
  84.                 {
  85.                     if (goldenPath[node.row][node.col] != null)
  86.                     {
  87.                         if (queue.Peek() == null || queue.Peek().value > node.value)
  88.                         {
  89.                             int rowStartGoldenPath = node.row;
  90.                             int colStartGoldenPath = node.col;
  91.                             int value = node.value;
  92.                             PriorityQueue queueReverse = new PriorityQueue();
  93.                             Node startNodeReverse = new Node(a[endRow][endCol], endRow, endCol);
  94.                             Node endNodeReverse = new Node(int.MaxValue, startRow, startCol);
  95.                             paths[startRow][startCol] = endNodeReverse;
  96.                             queueReverse.Enqueue(startNodeReverse);
  97.                             while (queueReverse.Count() > 0)
  98.                             {
  99.                                 if (queueReverse.Peek().value > endNodeReverse.value) break;
  100.                                 Node nodeReverse = queueReverse.Dequeue();
  101.                                 if (nodeReverse.isVisited) continue;
  102.                                 nodeReverse.isVisited = true;
  103.                                
  104.                                 if (goldenPath[nodeReverse.row][nodeReverse.col] != null && queueReverse.Peek().value > nodeReverse.value)
  105.                                 {
  106.                                     int result = value + nodeReverse.value;
  107.                                     while (rowStartGoldenPath != nodeReverse.row || colStartGoldenPath != nodeReverse.col)
  108.                                     {
  109.                                         nodeReverse = goldenPath[nodeReverse.parentRow][nodeReverse.parentCol];
  110.                                         result += nodeReverse.value;
  111.                                     }
  112.                                     return result;
  113.                                 }
  114.                                 if (nodeReverse.row > 0) PopulatePaths(a, paths, queueReverse, nodeReverse, -1, 0);
  115.                                 if (nodeReverse.row < paths.Length - 1) PopulatePaths(a, paths, queueReverse, nodeReverse, +1, 0);
  116.                                 if (nodeReverse.col > 0) PopulatePaths(a, paths, queueReverse, nodeReverse, 0, -1);
  117.                                 if (nodeReverse.col < paths[0].Length - 1) PopulatePaths(a, paths, queueReverse, nodeReverse, 0, +1);
  118.                                 paths[nodeReverse.row][nodeReverse.col] = nodeReverse;
  119.                             }
  120.                             return endNodeReverse.value;
  121.                         }
  122.                     }
  123.                 }
  124.                 if (node.row > 0) PopulatePaths(a, paths, queue, node, -1, 0);
  125.                 if (node.row < paths.Length - 1) PopulatePaths(a, paths, queue, node, +1, 0);
  126.                 if (node.col > 0) PopulatePaths(a, paths, queue, node, 0, -1);
  127.                 if (node.col < paths[0].Length - 1) PopulatePaths(a, paths, queue, node, 0, +1);
  128.             }
  129.             return endNode.value;
  130.         }
  131.  
  132.         static void PopulatePaths(int[][] a, Node[][] paths, PriorityQueue queue, Node node, int row, int col)
  133.         {
  134.             if (paths[node.row + row][node.col + col] == null)
  135.             {
  136.                 paths[node.row + row][node.col + col] = new Node(node.value + a[node.row + row][node.col + col], node.row + row, node.col + col);
  137.                 paths[node.row + row][node.col + col].parentRow = node.row;
  138.                 paths[node.row + row][node.col + col].parentCol = node.col;
  139.                 queue.Enqueue(paths[node.row + row][node.col + col]);
  140.             }
  141.             else
  142.             {
  143.                 if (paths[node.row + row][node.col + col].isFinish == true)
  144.                 {
  145.                     if (paths[node.row + row][node.col + col].value > paths[node.row][node.col].value + a[node.row + row][node.col + col])
  146.                     {
  147.                         paths[node.row + row][node.col + col].value = paths[node.row][node.col].value + a[node.row + row][node.col + col];
  148.                         paths[node.row + row][node.col + col].parentRow = node.row;
  149.                         paths[node.row + row][node.col + col].parentCol = node.col;
  150.                     }
  151.                 }
  152.             }
  153.         }
  154.  
  155.         public class Node
  156.         {
  157.             public int value;
  158.             public int row;
  159.             public int col;
  160.             public bool isVisited;
  161.             public bool isFinish;
  162.             public int parentRow;
  163.             public int parentCol;
  164.  
  165.             public Node(int value, int row, int col)
  166.             {
  167.                 this.value = value;
  168.                 this.row = row;
  169.                 this.col = col;
  170.                 this.parentRow = -1;
  171.                 this.parentCol = -1;
  172.             }
  173.         }
  174.  
  175.         public class PriorityQueue
  176.         {
  177.             private List<Node> data;
  178.  
  179.             public PriorityQueue()
  180.             {
  181.                 this.data = new List<Node>();
  182.             }
  183.  
  184.             public void Enqueue(Node item)
  185.             {
  186.                 data.Add(item);
  187.                 int ci = data.Count - 1;
  188.                 while (ci > 0)
  189.                 {
  190.                     int pi = (ci - 1) / 2;
  191.                     if (data[ci].value.CompareTo(data[pi].value) >= 0) break;
  192.                     Node tmp = data[ci]; data[ci] = data[pi]; data[pi] = tmp;
  193.                     ci = pi;
  194.                 }
  195.             }
  196.  
  197.             public Node Dequeue()
  198.             {
  199.                 int li = data.Count - 1;
  200.                 Node frontItem = data[0];
  201.                 data[0] = data[li];
  202.                 data.RemoveAt(li);
  203.  
  204.                 --li;
  205.                 int pi = 0;
  206.                 while (true)
  207.                 {
  208.                     int ci = pi * 2 + 1;
  209.                     if (ci > li) break;
  210.                     int rc = ci + 1;
  211.                     if (rc <= li && data[rc].value.CompareTo(data[ci].value) < 0)
  212.                         ci = rc;
  213.                     if (data[pi].value.CompareTo(data[ci].value) <= 0) break;
  214.                     Node tmp = data[pi]; data[pi] = data[ci]; data[ci] = tmp;
  215.                     pi = ci;
  216.                 }
  217.                 return frontItem;
  218.             }
  219.  
  220.             public Node Peek()
  221.             {
  222.                 return data.Count() > 0 && data[0] != null ? data[0] : null;
  223.             }
  224.  
  225.             public int Count()
  226.             {
  227.                 return data.Count;
  228.             }
  229.  
  230.             public bool IsConsistent()
  231.             {
  232.                 if (data.Count == 0) return true;
  233.                 int li = data.Count - 1;
  234.                 for (int pi = 0; pi < data.Count; ++pi)
  235.                 {
  236.                     int lci = 2 * pi + 1;
  237.                     int rci = 2 * pi + 2;
  238.  
  239.                     if (lci <= li && data[pi].value.CompareTo(data[lci].value) > 0) return false;
  240.                     if (rci <= li && data[pi].value.CompareTo(data[rci].value) > 0) return false;
  241.                 }
  242.                 return true;
  243.             }
  244.         } // Priority
  245.     }
  246. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top