const rl = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout
});

const inputs = [];
const dr = [{x: -1, y: 0}, { x: 0, y: 1 }, { x: 1, y: 0 }, {x: 0, y: -1}];

rl.on('line', (line) => {
    inputs.push(line);
}).on('close', () => {
    // 1. 初始化迷宫
    const maze = initMaza(inputs);
    // 2. dfs
    dfs(maze, 0, 0);
});

// 题目要求是左上角到右下角，所以起点和终点是固定
function dfs(maze, i, j, visited = ['(0,0)']) {
    const row = maze.length, col = maze[0].length;

    // 终止条件
    if(i == row - 1 && j == col -1) {
        // 输出路径
        visited.forEach(item => {
            console.log(item);
        })
        return;
    }
    // // up
    // if(i-1 >= 0 && maze[i-1][j] == 0 && !visited.includes(`(${i-1},${j})`)) {
    //     visited.push(`(${i-1},${j})`);
    //     dfs(maze, i-1, j, visited);
    //     visited.pop();
    // }
    // // right
    // if(j+1 < col && maze[i][j+1] == 0 && !visited.includes(`(${i},${j+1})`)) {
    //     visited.push(`(${i},${j+1})`);
    //     dfs(maze, i, j+1, visited);
    //     visited.pop();
    // }
    // // down
    // if(i+1 < row && maze[i+1][j] == 0 && !visited.includes(`(${i+1},${j})`)) {
    //     visited.push(`(${i+1},${j})`);
    //     dfs(maze, i+1, j, visited);
    //     visited.pop();
    // }
    // // left
    // if(j-1 >= 0 && maze[i][j-1] == 0 && !visited.includes(`(${i},${j-1})`)) {
    //     visited.push(`(${i},${j-1})`);
    //     dfs(maze, i, j-1, visited);
    //     visited.pop();
    // }
    // 简化上面四个方向的代码
    for(let k = 0; k < 4; k++) {
        const x = i + dr[k].x, y = j + dr[k].y;
        if(x >= 0 && x < row && y >= 0 && y < col &&
            maze[x][y] == 0 &&
            !visited.includes(`(${x},${y})`)
        ) {
            visited.push(`(${x},${y})`);
            dfs(maze, x, y, visited);
            visited.pop();
        }
    }
    return;
}

function initMaza(inputs) {
    const rAc = inputs[0].split(' ');
    row = rAc[0];
    col = rAc[1];
    const maze = [];

    for(let i = 1; i <= row; i++) {
        maze.push(inputs[i].split(' '));
    }

    return maze;
}

难度：⭐⭐⭐

思路：

DFS 本质其实还是枚举，枚举所有的可能性。这道题，从(0,0)点出发，朝四个方向一步一步的试探，如果最后试探到了终点就打印这次试探中的路径。

DFS模板：

DFS(...可能需要的参数) {
	if(终止条件) {
	  // 可能需要做些其它，比如打印记录
		return; // 是否有返回也根据实际情况来，一般返回Boolean类型，一层一层往上回溯传递条件
	}
  for(....) {
  	// 进行操作，比如
	visited.push(i, i);
	// 递归
	DFS(...) 
	// 回溯
	visited.pop()
  }
  
  return;
}