1 files changed, 73 insertions, 0 deletions
diff --git a/2ndary/12/TP-HN-2008/R2/hc.cpp b/2ndary/12/TP-HN-2008/R2/hc.cpp
new file mode 100644
index 0000000..1ea6ee3
--- /dev/null
+++ b/2ndary/12/TP-HN-2008/R2/hc.cpp
@@ -0,0 +1,73 @@
+#include <iostream>
+#include <fstream>
+#include <functional>
+#include <queue>
+#include <vector>
+
+#define ENC(a, x, y) (((a) << 16) + ((x) << 8) + (y))
+
+using namespace std;
+
+int
+main()
+{
+  long long m, n, i, j, a[200][200];
+  ifstream infile;
+  infile.open("HC.INP");
+  infile >> m >> n;
+  for (i = 0; i < m; i++)
+    for (j = 0; j < n; j++)
+      infile >> a[i][j];
+  infile.close();
+
+  priority_queue<long long, vector<long long>, greater<long long>> heap;
+  long long path[200][200] = {};
+  for (i = 0; i < m; i++)
+    {
+      heap.push(ENC(*a[i], i, 0));
+      path[i][0] = 1;
+    }
+
+  long long tmp, x, y;
+  while (!heap.empty())
+    {
+      tmp = heap.top();
+      heap.pop();
+      x = tmp >> 8 & 255;
+      y = tmp & 255;
+      tmp >>= 16;
+      if (y == n - 1)
+        break;
+
+      if (!path[x][y + 1])
+        {
+          heap.push(ENC(tmp + a[x][y + 1], x, y + 1));
+          path[x][y + 1] = 1;
+        }
+
+      if (y)
+        if (x && !path[x - 1][y])
+          {
+            heap.push(ENC(tmp + a[x - 1][y], x - 1, y));
+            path[x - 1][y] = 1;
+          }
+        else if (x < m - 1 && !path[x + 1][y])
+          {
+            heap.push(ENC(tmp + a[x + 1][y], x + 1, y));
+            path[x + 1][y] = 1;
+          }
+
+      if (y > 1 && !path[x][y - 1])
+        {
+          heap.push(ENC(tmp + a[x][y - 1], x, y - 1));
+          path[x][y - 1] = 1;
+        }
+    }
+
+  ofstream outfile;
+  outfile.open("HC.OUT");
+  outfile << tmp << endl;
+  outfile.close();
+
+  return 0;
+}