const dy = [-1, 0, 1,  0];
const dx = [ 0, 1, 0, -1];
function solve(map){
    let alreadyVisited = new Set();
    function serializePoint(y, x){
        return x + "," + y;
    }
    let route = [];
    function dfs(y, x){
        // ゴールを発見したら，例外で脱出する
        if(map[y][x] == GOAL){
            throw new Route(route);
        }
        // もうそれより先にいってたら，中断
        if(alreadyVisited.has(serializePoint(y, x))){
            return;
        }
        alreadyVisited.add(serializePoint(y, x));
        // 4方向試す
        for(var i=0; i<4; i++){
            // 氷に乗っていけるところまでいってみる
            const ddy = dy[i];
            const ddx = dx[i];
            let ny = y;
            let nx = x;
            // 岩にあたるまでまっすぐ．(本当は g とかも考慮しないといけんね．)
            while(map[ny][nx] != WALL){
                ny += ddy;
                nx += ddx;
            }
            // いきすぎなのでもどる
            ny -= ddy;
            nx -= ddx;
            // 動けたらそれより先に dfs
            if(!(y == ny && x == nx)){
                // あとで表示するように今の場所をいれる
                route.push([ny, nx]);
                dfs(ny, nx);
                // どうやらこれより先には答はなかったみたいなので
                // 今の場所を破棄
                route.pop();
            }
        }
    }
    function findStart(){
        let ret = [];
        for(let y=0; y<map.length; y++){
            for(let x=0; x<map[y].length; x++){
                if(map[y][x] == START){
                    ret.push([y, x]);
                }
            }
        }
        return ret;
    }
    try {
        // スタートは複数あるかも？
        for(let start of findStart()){
            route = [start];
            dfs(start[0], start[1]);
        }
    } catch(e) { // found
        if(e instanceof Route){
            console.log(e.route);
            console.log("found");
            return e.route;
        }
        throw(e);
    }
    return null;
}