import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int a = in.nextInt(); int b = in.nextInt(); int[][] grd = new int[a + 2][b + 2];//在地图外包围一圈1,便于判断 //地图初始化 for (int i = 1; i <= a; i++) { for (int j = 1; j <= b; j++) { int t = in.nextInt(); grd[i][j] = t; } } for (int i = 0; i < a + 2; i++) { grd[i][0] = 1; grd[i][b + 1] = 1; } for (int j = 0; j < b + 2; j++) { grd[0][j] = 1; grd[a + 1][j] = 1; } //初始化队列 链表表头 节点指针 Queue<Node> que = new LinkedList<Node>(); Node head = new Node(1, 1, null); que.offer(head); Node temp; //广度优先搜索 do { temp = que.poll(); grd[temp.a][temp.b] = 1;//走过的坐标换成1 if (grd[temp.a + 1][temp.b] == 0) {//下 Node node = new Node(temp.a + 1, temp.b, temp); que.offer(node); } if (grd[temp.a - 1][temp.b] == 0) {//上 Node node = new Node(temp.a - 1, temp.b, temp); que.offer(node); } if (grd[temp.a][temp.b + 1] == 0) {//右 Node node = new Node(temp.a, temp.b + 1, temp); que.offer(node); } if (grd[temp.a][temp.b - 1] == 0) {//左 Node node = new Node(temp.a, temp.b - 1, temp); que.offer(node); } } while (!(temp.a == a && temp.b == b)); //用栈来存储以及将反向查找的路径归正 Stack<Node> res = new Stack<Node>(); do{ res.push(temp); temp = temp.pre; }while(temp.pre != null); System.out.println("(0,0)");//起点 do{ Node out = res.pop(); int ao = out.a -1; int bo = out.b -1; System.out.println("("+ao+","+bo+")"); }while(!res.isEmpty()); } } class Node {//用pre代替next,节点指向上一个节点,便于反推最短路径 int a; int b; Node pre; public Node(int a, int b, Node pre) { this.a = a; this.b = b; this.pre = pre; } }