ㄠㄨ抓老鼠

題目敘述

給你一個N*M的迷宮地圖，我們用#來表示障礙物、.表示可走的路、&表示ㄠㄨ、@表示老鼠。保證ㄠㄨ走到老鼠只有一條路徑，且邊框都用障礙物圍住。最左上角的格子編號為(0,0)，最右下角的格子編號為(N-1,M-1)。

請你找出ㄠㄨ從他所在的位置走到老鼠的位置得最短路線。

輸入說明

第一行有兩個數字$N,M$，$1 \leq N,M \leq 1001$，接著會有一個N*M的迷宮，保證一定有一隻ㄠㄨ一隻老鼠

輸出說明

第一行請輸出ㄠㄨ到老鼠的最短距離，接著請按造順序輸出ㄠㄨ到老鼠的路徑上會經過的格子點，記得要換行。

範例輸入 1

15 13
#############
#.........#.#
#.###.#.#.#.#
#...#.#.#@#.#
#.###.#.###.#
#.#...#...#.#
#.#######.#.#
#...#.......#
#.#####.#.#.#
#.....#.#.#.#
###.#####.#.#
#.....#&#.#.#
#####.#.###.#
#.....#.....#
#############

範例輸出 1

27
(11,7)
(12,7)
(13,7)
(13,8)
(13,9)
(13,10)
(13,11)
(12,11)
(11,11)
(10,11)
(9,11)
(8,11)
(7,11)
(7,10)
(7,9)
(6,9)
(5,9)
(5,8)
(5,7)
(4,7)
(3,7)
(2,7)
(1,7)
(1,8)
(1,9)
(2,9)
(3,9)

範例輸入 2

25 25
#########################
#&#@#.....#.....#...#...#
#.#.#.#.#####.#.#.###.###
#.....#.......#.......#.#
#####.#####.#######.#.#.#
#...#.#...#.#.......#.#.#
#.#.#####.#.#######.###.#
#.#.......#.....#.......#
#####.#####.#######.#####
#.........#.....#...#...#
###.#############.#.#.#.#
#.................#.#.#.#
#.#####.#.#####.#####.###
#.#.....#...#...#...#...#
###########.#.#####.#.#.#
#...........#.........#.#
#.#.#.#####.#####.#.#####
#.#.#.....#.....#.#.....#
###.#.#.###.#.###.#####.#
#...#.#...#.#.#.......#.#
###############.#.#.###.#
#.....#.......#.#.#...#.#
###.#.#.#.#.#.#.#####.#.#
#...#...#.#.#.......#.#.#
#########################

範例輸出 2

7
(1,1)
(2,1)
(3,1)
(3,2)
(3,3)
(2,3)
(1,3)

配分方法

• 20% $N,M \leq 25$
• 20% $N,M \leq 101$
• 60% $N,M \leq 1001$

提示

備註

Judge Setting