#!/usr/bin/env /friends/bin/cxxscript

#include <iostream>
using namespace std;

constexpr int MAP_SIZE = 5;    // マップの縦横のサイズ

// mapを描画
void display(const int map[MAP_SIZE][MAP_SIZE]) {
    for (int y = 0; y < MAP_SIZE; y++) {
        for (int x = 0; x < MAP_SIZE; x++) {
            switch (map[y][x]) {
                case 0: cout << "＿"; break;
                case 1: cout << "■"; break;
                case 2: cout << "me"; break;
                case 3: cout << "◆"; break;
            }
        }
        cout << endl;
    }
}

// その場所が通過できる場所か
bool passMap(const int map[MAP_SIZE][MAP_SIZE], const int x, const int y) {
    if (0 <= x && x < MAP_SIZE && 0 <= y && y < MAP_SIZE) {
        switch (map[y][x]) {
            case 1: return false; break;    // ■のみ通過不可
            default: return true; break;
        }
    }
    return false;
}

// 問題のアルゴリズム
// ゴールまでの道のりを探索する　幅優先探索
bool searchRoute(const int map[MAP_SIZE][MAP_SIZE], int route[MAP_SIZE][MAP_SIZE], int sx, int sy, int gx, int gy) {
    if (!passMap(map, sx, sy)) return false;
    route[sy][sx] = 1;
    if (sx == gx && sy == gy) return true;
    if (searchRoute(map, route, sx, sy-1, gx, gy)) return true;
    if (searchRoute(map, route, sx, sy+1, gx, gy)) return true;
    if (searchRoute(map, route, sx-1, sy, gx, gy)) return true;
    if (searchRoute(map, route, sx+1, sy, gx, gy)) return true;
    route[sy][sx] = 0;
    return false;
}

int main() {
    // 0:道 1:壁 2:自分 3:ゴール
    int map[MAP_SIZE][MAP_SIZE] = {
        {0, 2, 0, 0, 0},
        {0, 0, 1, 0, 0},
        {0, 1, 0, 0, 0},
        {0, 0, 0, 1, 0},
        {0, 0, 1, 3, 0}
    };

    display(map);
    int route[MAP_SIZE][MAP_SIZE];    // 道のりを保存する配列
    for (int i = 0; i < MAP_SIZE; i++) {
        for (int j = 0; j < MAP_SIZE; j++)
            route[i][j] = 0;
    }
    searchRoute(map, route, 1, 0, 3, 4);
    cout << endl;
    display(route);

    return 0;
}