using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("2 3");
WillReturn.Add("0 6 4");
WillReturn.Add("2 3 0");
//7
//..#
//.#.
}
else if (InputPattern == "Input2") {
WillReturn.Add("4 3");
WillReturn.Add("0 9 2");
WillReturn.Add("9 3 9");
WillReturn.Add("2 3 9");
WillReturn.Add("3 9 0");
//7
//..#
//.#.
//#..
//...
}
else if (InputPattern == "Input3") {
WillReturn.Add("2 2");
WillReturn.Add("0 1000000000");
WillReturn.Add("1000000000 0");
//2000000000
//.#
//#.
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long UB_X;
static long UB_Y;
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
UB_Y = wkArr[0] - 1;
UB_X = wkArr[1] - 1;
long[,] CostArr = CreateBanArr(InputList.Skip(1));
long?[,] MinCostArr = new long?[UB_X + 1, UB_Y + 1];
long?[,] ParentNodeArr = new long?[UB_X + 1, UB_Y + 1];
var InsPQueue_Arr = new PQueue_Arr();
PQueue_Arr.PQueueJyoutaiDef WillEnqueue;
for (long X = 1; X <= UB_X; X++) {
WillEnqueue.CurrX = X;
WillEnqueue.CurrY = 0;
WillEnqueue.Val = CostArr[X, 0];
InsPQueue_Arr.Enqueue(WillEnqueue);
MinCostArr[X, 0] = CostArr[X, 0];
}
for (long Y = 0; Y <= UB_Y - 1; Y++) {
WillEnqueue.CurrX = UB_X;
WillEnqueue.CurrY = Y;
WillEnqueue.Val = CostArr[UB_X, Y];
InsPQueue_Arr.Enqueue(WillEnqueue);
MinCostArr[UB_X, Y] = CostArr[UB_X, Y];
}
long Answer = long.MaxValue;
long GoalX = -1;
long GoalY = -1;
while (InsPQueue_Arr.Count() > 0) {
PQueue_Arr.PQueueJyoutaiDef Dequeued = InsPQueue_Arr.Dequeue();
long CurrX = Dequeued.CurrX;
long CurrY = Dequeued.CurrY;
// クリア判定
if (CurrX == 0 || CurrY == UB_Y) {
Answer = Math.Min(Answer, Dequeued.Val);
GoalX = CurrX;
GoalY = CurrY;
break;
}
List<PointDef> KinbouList = Get8KinbouList(CurrX, CurrY);
foreach (PointDef EachPoint in KinbouList) {
if (EachPoint.X == 0 && EachPoint.Y == 0) continue;
if (EachPoint.X == UB_X && EachPoint.Y == UB_Y) continue;
long NewCost = Dequeued.Val + CostArr[EachPoint.X, EachPoint.Y];
if (MinCostArr[EachPoint.X, EachPoint.Y].HasValue) {
if (NewCost >= MinCostArr[EachPoint.X, EachPoint.Y].Value) {
continue;
}
}
MinCostArr[EachPoint.X, EachPoint.Y] = NewCost;
long ParentHash = GetHash(CurrX, CurrY);
ParentNodeArr[EachPoint.X, EachPoint.Y] = ParentHash;
WillEnqueue.CurrX = EachPoint.X;
WillEnqueue.CurrY = EachPoint.Y;
WillEnqueue.Val = NewCost;
InsPQueue_Arr.Enqueue(WillEnqueue);
}
}
Console.WriteLine(Answer);
char[,] AnswerArr = new char[UB_X + 1, UB_Y + 1];
for (long X = 0; X <= UB_X; X++) {
for (long Y = 0; Y <= UB_Y; Y++) {
AnswerArr[X, Y] = '.';
}
}
while (true) {
AnswerArr[GoalX, GoalY] = '#';
if (ParentNodeArr[GoalX, GoalY].HasValue) {
long ParentHash = ParentNodeArr[GoalX, GoalY].Value;
GoalX = ParentHash / 1000;
GoalY = ParentHash % 1000;
}
else break;
}
PrintBan(AnswerArr);
}
// 座標のハッシュ値
static long GetHash(long pX, long pY)
{
return pX * 1000 + pY;
}
struct PointDef
{
internal long X;
internal long Y;
}
// 8近傍の座標を返す
static List<PointDef> Get8KinbouList(long pX, long pY)
{
var WillReturn = new List<PointDef>();
WillReturn.AddRange(GetPoint(pX - 1, pY - 1));
WillReturn.AddRange(GetPoint(pX + 0, pY - 1));
WillReturn.AddRange(GetPoint(pX + 1, pY - 1));
WillReturn.AddRange(GetPoint(pX - 1, pY + 0));
WillReturn.AddRange(GetPoint(pX + 1, pY + 0));
WillReturn.AddRange(GetPoint(pX - 1, pY + 1));
WillReturn.AddRange(GetPoint(pX + 0, pY + 1));
WillReturn.AddRange(GetPoint(pX + 1, pY + 1));
return WillReturn;
}
static List<PointDef> GetPoint(long pTargetX, long pTargetY)
{
var WillReturn = new List<PointDef>();
if (pTargetX < 0 || UB_X < pTargetX) return WillReturn;
if (pTargetY < 0 || UB_Y < pTargetY) return WillReturn;
PointDef WillAdd;
WillAdd.X = pTargetX;
WillAdd.Y = pTargetY;
WillReturn.Add(WillAdd);
return WillReturn;
}
////////////////////////////////////////////////////////////////
// IEnumerable<string>をlongの2次元配列に設定
////////////////////////////////////////////////////////////////
static long[,] CreateBanArr(IEnumerable<string> pStrEnum)
{
var StrList = new List<string>(pStrEnum);
if (StrList.Count == 0) {
return new long[0, 0];
}
long[] LongArr = { };
Action<string> SplitAct = pStr =>
LongArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
SplitAct(StrList[0]);
long UB_X = LongArr.GetUpperBound(0);
long UB_Y = StrList.Count - 1;
long[,] WillReturn = new long[UB_X + 1, UB_Y + 1];
for (long Y = 0; Y <= UB_Y; Y++) {
SplitAct(StrList[(int)Y]);
for (long X = 0; X <= UB_X; X++) {
WillReturn[X, Y] = LongArr[X];
}
}
return WillReturn;
}
////////////////////////////////////////////////////////////////
// 2次元配列(char型)のデバッグ出力
////////////////////////////////////////////////////////////////
static void PrintBan(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
sb.Append(pBanArr[X, Y]);
}
sb.AppendLine();
}
Console.Write(sb.ToString());
}
}
#region PQueue_Arr
// 内部で配列使用の優先度付きキュー (根のValが最小)
internal class PQueue_Arr
{
internal struct PQueueJyoutaiDef
{
internal long CurrX;
internal long CurrY;
internal long Val;
}
private PQueueJyoutaiDef[] mHeapArr;
private long mHeapArrCnt = 0;
// コンストラクタ
internal PQueue_Arr()
{
mHeapArr = new PQueueJyoutaiDef[65535];
}
internal bool IsEmpty()
{
return mHeapArrCnt == 0;
}
internal long Count()
{
return mHeapArrCnt;
}
internal long Peek()
{
return mHeapArr[1].Val;
}
// エンキュー処理
internal void Enqueue(PQueueJyoutaiDef pAddJyoutai)
{
long CurrNode = 1 + mHeapArrCnt;
if (mHeapArr.GetUpperBound(0) < CurrNode) {
ExtendArr();
}
mHeapArr[CurrNode] = pAddJyoutai;
mHeapArrCnt++;
while (1 < CurrNode && mHeapArr[CurrNode / 2].Val > mHeapArr[CurrNode].Val) {
PQueueJyoutaiDef Swap = mHeapArr[CurrNode];
mHeapArr[CurrNode] = mHeapArr[CurrNode / 2];
mHeapArr[CurrNode / 2] = Swap;
CurrNode /= 2;
}
}
// 配列のExtend
private void ExtendArr()
{
PQueueJyoutaiDef[] NewHeapArr = new PQueueJyoutaiDef[mHeapArrCnt * 2];
mHeapArr.CopyTo(NewHeapArr, 0);
mHeapArr = NewHeapArr;
}
// デキュー処理
internal PQueueJyoutaiDef Dequeue()
{
PQueueJyoutaiDef TopNode = mHeapArr[1];
long LastNode = mHeapArrCnt;
mHeapArr[1] = mHeapArr[LastNode];
mHeapArrCnt--;
MinHeapify(1);
return TopNode;
}
// 根ノードを指定し、根から葉へヒープ構築
private void MinHeapify(long pRootNode)
{
if (mHeapArrCnt <= 1) {
return;
}
long Left = pRootNode * 2;
long Right = pRootNode * 2 + 1;
// 左の子、自分、右の子で値が最小のノードを選ぶ
long Smallest = mHeapArr[pRootNode].Val;
long SmallestNode = pRootNode;
if (Left <= mHeapArrCnt && mHeapArr[Left].Val < Smallest) {
Smallest = mHeapArr[Left].Val;
SmallestNode = Left;
}
if (Right <= mHeapArrCnt && mHeapArr[Right].Val < Smallest) {
Smallest = mHeapArr[Right].Val;
SmallestNode = Right;
}
// 子ノードのほうが小さい場合
if (SmallestNode != pRootNode) {
PQueueJyoutaiDef Swap = mHeapArr[SmallestNode];
mHeapArr[SmallestNode] = mHeapArr[pRootNode];
mHeapArr[pRootNode] = Swap;
// 再帰的に呼び出し
MinHeapify(SmallestNode);
}
}
}
#endregion