思路：
1. BFS求最短路
2. 记录路径， 开一个pre二维数组， 记录当前点的是从哪个点过来的

技巧：
1. 反向BFS,从终点走到起点， 这样打印路径更方便。
2. java 没有c ++ 的pair函数， 自己写太麻烦
加入一个映射关系， 把坐标点映射成 数字， 数字反映射成左边点， 详情看代码。

import java.io.*;
import java.util.*;
class Main{
    static int INF = 1010, row, col;
    static int[][] a = new int[INF][INF], pre = new int[INF][INF];

    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[][] dir = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public static void bfs(int r, int c, int n){
        for(int i = 0; i < n; i++) Arrays.fill(pre[i], -1);
        Queue<Integer> q = new LinkedList();
        int re = reflect(r, c);
        q.offer(re);
        while(!q.isEmpty()){
            int poll = q.poll();
            int[] de = deflect(poll);
            int x = de[0], y = de[1];
            for(int i = 0; i < 4; i++){
                int nx = x + dir[i][0], ny = y + dir[i][1];
                if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                if(a[nx][ny] != 0 || pre[nx][ny] != -1) continue;

                re = reflect(nx, ny);
                pre[nx][ny] = poll;
                q.offer(re);
            }
        }
    }

    public static void main(String[] args) throws Exception{
        int n = Integer.valueOf(read.readLine());
        col = row = n;
        for(int i = 0; i < n; i++){
            String[] ss = read.readLine().split(" ");
            for(int j = 0; j < n; j++){
                a[i][j] = Integer.valueOf(ss[j]);
            }
        }
        bfs(n - 1, n - 1, n);

        int cur = 0, end = n * n - 1;
        while(true){
            int[] out = deflect(cur);
            log.write(out[0] + " " + out[1] + "\n");
            if(cur == end) break;
            cur = pre[out[0]][out[1]];
        }
        log.flush();
    }

    //把数字映射成坐标
    public static int[] deflect(int a){
        return new int[]{a / col, a % col};
    }
    //把坐标映射成数字
    public static int reflect(int x, int y){
        return x * col + y;
    }
}