/*
  g++ -g wf.cpp -o wf
 
  ワーシャル-フロイド法
  (ダイクストラは個別ルートでは早いが、先に全ルート計算しておくなら、
  こっちの方法の法が速いこともある)
  
  と、
 
  STLのリストの使い方(ファンクションへのリストの渡し方とか、リストの複製の作り方とか)
  などの、便利な技が仕込まれているので貼っておく
 
 
 
*/
 
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <list>   // list 利用のため
 
using namespace std;
 
//int d[100][100];  // d[i][k]：ノードiからノードkへの距離 
//int via[100][100];  // d[i][k]の間にある(少くとも1つの)中継ノード
 
double d[100][100];  // d[i][k]：ノードiからノードkへの距離 
int via[100][100];  //  d[i][k]の間にある(少くとも1つの)中継ノード
 
list<int> path[100][100];   // int 型の list を宣言  
 
 
#if 1
// 中継パスの表示ルーチン(再帰呼出し用)
void printPath1_aux(int begin, int end) {
  if (via[begin][end] == begin) {
	if (begin != end)
	  printf("%02d -> ", begin);
	return;
  }
  
  printPath1_aux(begin, via[begin][end]);
  printPath1_aux(via[begin][end], end);
}
#endif
 
// 中継パスの表示ルーチン(再帰呼出し用)
void printPath1_aux(int begin, int end, list<int>* p) {
  if (via[begin][end] == begin) {
	if (begin != end){
	  // printf("%02d -> ", begin);
	  p->push_back(begin);
	}
	return;
  }
  
  printPath1_aux(begin, via[begin][end], p);
  printPath1_aux(via[begin][end], end, p);
}
 
 
 
// 中継パスの表示ルーチン
#if 1
void printPath1(int start, int goal) {
  printPath1_aux(start, via[start][goal]);
  printPath1_aux(via[start][goal], goal);
  printf("%02d\n", goal);
}
#endif 
 
void printPath1(int start, int goal, list<int> *p ) {
  printPath1_aux(start, via[start][goal], p);
  printPath1_aux(via[start][goal], goal, p);
  // printf("%02d\n", goal);
  p->push_back(goal);
 
}
 
 
int main(void)
{
  // 変数の初期化
  for(int i = 0; i < 100; i++){
	for(int j = 0; j < 100; j++){
	  d[i][j] = 999.9; // 距離の初期化(でっかい値を入力しておく(INT_MAXは足し算の時に桁上がりが起こるので使わない)
	  via[i][j] = i; // ノードiからノードkへの経由値の初期化 
	}
  }
 
 #if 0
  // 確認用の表示
  printf("\n[STEP1]\n");
 
  for(int i = 0; i < 100; i++){
	for(int k = 0; k < 100; k++){
	  printf("d[%d][%d]):%f\t",i,k,d[i][k]);
	  printf("via[%d][%d]):%d\n",i,k,via[i][k]);
	}
  }
#endif
 
  //// ここからは実際の距離を手書き
 
  for(int i = 0; i < 100; i++){
	d[i][i] = 0; //// 同じノードへの距離は0になるので、上書き
  }
 
  //ノード番号の通番を以下のようにする
  // [0][2] → "02", [4][9] → "49", [9][[9] → "99"
  // 座標は1ケタ内に留める
 
  for (int y = 0; y < 5; y++){
	for (int x = 0; x < 9; x++){
 
	  int n_num = x * 10 + y;
 
	  // + ( 1, 0)
	  int x_new = x + 1;
	  int y_new = y;
 
	  if (x_new < 9){
		int n_num_next = x_new * 10 + y_new;
		d[n_num][n_num_next] = 0.25;
		
		printf("1:d[%02d][%02d]=%f\n",n_num, n_num_next, d[n_num][n_num_next]);
 
	  }
 
	  // + (-1, 0)
	  x_new = x - 1;
	  y_new = y;
 
	  if (x_new > -1 ){
		int n_num_next = x_new * 10 + y_new;
		d[n_num][n_num_next] = 0.25;
		printf("2:d[%02d][%02d]=%f\n",n_num, n_num_next, d[n_num][n_num_next]);
	  }
 
	  // + ( 0, 1)
	  x_new = x;
	  y_new = y + 1;
 
	  if (y_new < 5 ){
		int n_num_next = x_new * 10 + y_new;
		d[n_num][n_num_next] = 0.25;
		printf("3:d[%02d][%02d]=%f\n",n_num, n_num_next, d[n_num][n_num_next]);
	  }
 
	  // + ( 0,-1)
	  x_new = x;
	  y_new = y - 1;
 
	  if (y_new > -1 ){
		int n_num_next = x_new * 10 + y_new;
		d[n_num][n_num_next] = 0.25;
		printf("4:d[%02d][%02d]=%f\n",n_num, n_num_next, d[n_num][n_num_next]);
	  }
	}
  }
 
  // 実験用上書き
  d[02][12] = 0.1;  
  d[12][22] = 0.1;  
  d[22][32] = 0.1;  
  d[32][42] = 0.1;  
  d[42][52] = 0.1;  
  d[52][62] = 0.1;  
  d[62][72] = 0.1;  
  d[72][82] = 0.1;  
 
  d[12][02] = 0.1;  
  d[22][12] = 0.1;  
  d[32][22] = 0.1;  
  d[42][32] = 0.1;  
  d[52][42] = 0.1;  
  d[62][52] = 0.1;  
  d[72][62] = 0.1;  
  d[82][72] = 0.1;  
 
 
#if 0
  // 確認用の表示
  printf("\n[STEP2]\n");
 
  for(int i = 0; i < 99; i++){
	for(int k = 0; k < 99; k++){
	  printf("d[%d][%d]):%f\t",i,k,d[i][k]);
	  printf("via[%d][%d]):%d\n",i,k,via[i][k]);
	}
  }
#endif
 
 
  // 経路長計算
  for (int k =0; k < 99; k++){  
	for (int i =0; i < 99; i++){
	  for(int j = 0; j < 99; j++){
		if(d[i][j] > d[i][k] + d[k][j]){
		  d[i][j] = d[i][k] + d[k][j];
		  via[i][j] = k; //更新処理
		}
	  }
	}
  }
 
 
#if 0
  // 計算結果
  printf("\n[STEP3]\n");
 
  for(int i = 0; i < 99; i++){
	for(int k = 0; k < 99; k++){
	  printf("d[%d][%d]):%f\t",i,k,d[i][k]);
	  printf("via[%d][%d]):%d\n",i,k,via[i][k]);
	}
  }
#endif 
 
#if 1
  // 経路パス表示
  printf("\n[Path]\n");
  for(int i = 0; i < 99; i++){
	for(int k = 0; k < 99; k++){
	  if (d[i][k] < 99.9){
		printf("d[%02d][%02d]:%f ",i,k,d[i][k]);
		printPath1(i, k);
		printPath1(i, k, &(path[i][k]));
	  }
	}
  }
#endif
  
  
  // イテレータ (反復子) の定義
  list<int>::iterator pos;
 
  list<int> l = path[83][04];
  // イテレータをずらしながら、全てのデータを取り出す。
  for(pos = l.begin(); pos!=l.end(); ++pos){
      cout << *pos << "\n";
  }
 
  printf("\n");
 
 
  // https://cpprefjp.github.io/reference/algorithm/copy.html
  // back_inserter を使って l2 へ設定。
  // back_inserter は要素をコピーするときに l2.push_back() するイテレータを作る関数。
  std::list<int> l2;
  std::copy(l.begin(), l.end(), back_inserter(l2));
 
  // l2.erase(v.begin() + 2);       //  3番目の要素（9）を削除
  l2.erase(l2.begin());       // 先頭の要素を削除
 
 
  for(pos = l2.begin(); pos!=l2.end(); ++pos){
      cout << *pos << "\n";
  }
 
 
}