[入力例]
2 2
..
..
[出力例(debug版)]
0 1
1 2
1
[入力例]
3 4
..#.
..#.
.#..
[出力例(debug版)]
0 1 0 0
1 2 0 0
2 0 0 0
-1
[入力例]
3 3
..#
#..
...
[出力例(debug版)]
0 1 0
0 2 3
4 3 4
2
※AtCoderテストケースより
[入力例]
10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................
[出力例(debug版)]
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
1 2 3 0 5 6 7 0 0 0 0 12 13 14 0 0 0 0 19 20 0 0 0 24 25 26 0 0 0 30 31 32 0 0 0 36 37
2 3 0 0 0 7 8 0 0 0 0 0 14 0 0 23 22 21 20 0 0 0 0 0 26 0 0 0 0 0 32 0 0 0 0 0 38
3 4 0 0 0 8 9 0 0 0 0 0 15 0 25 24 23 22 21 0 0 0 0 0 27 0 0 0 0 0 33 0 0 0 0 0 39
4 0 0 0 0 0 10 0 0 0 0 0 16 0 26 25 24 23 22 0 0 0 0 0 28 0 0 0 0 0 34 0 0 0 0 0 40
5 0 0 0 0 0 11 0 0 0 0 18 17 0 27 26 25 24 23 0 0 0 0 0 29 30 0 0 37 36 35 36 0 0 43 42 41
6 0 14 15 16 0 12 0 0 0 0 0 18 0 28 27 26 25 24 0 0 0 0 0 30 0 40 39 38 0 36 0 46 45 44 0 42
7 0 13 14 15 0 13 0 0 0 0 0 19 0 0 28 27 26 25 0 0 0 0 0 31 0 41 40 39 0 37 0 47 46 45 0 43
8 0 12 13 14 0 14 0 0 0 0 21 20 21 0 0 0 0 26 27 0 0 0 33 32 33 0 0 0 39 38 39 0 0 0 45 44
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
209
※AtCoderテストケースより
[入力例]
50 50
..................................................
...#...####...####.#####..#####.######.######.....
..#.#..#...#.##....#....#.#.....#......#....#.....
..#.#..#...#.#.....#....#.#.....#......#....#.....
.#...#.#..##.#.....#....#.#####.#####..#..........
.#####.####..#.....#....#.#.....#......#..###.....
.#...#.#...#.#.....#....#.#.....#......#....#.....
.#...#.#...#.##....#....#.#.....#......#....#.....
.#...#.####...####.#####..#####.#......######.....
..................................................
..................................................
...#...####...####.#####..#####.######.######.....
..#.#..#...#.##....#....#.#.....#......#....#.....
..#.#..#...#.#.....#....#.#.....#......#....#.....
.#...#.#..##.#.....#....#.#####.#####..#..........
.#####.####..#.....#....#.#.....#......#..###.....
.#...#.#...#.#.....#....#.#.....#......#....#.....
.#...#.#...#.##....#....#.#.....#......#....#.....
.#...#.####...####.#####..#####.#......######.....
..................................................
..................................................
...#...####...####.#####..#####.######.######.....
..#.#..#...#.##....#....#.#.....#......#....#.....
..#.#..#...#.#.....#....#.#.....#......#....#.....
.#...#.#..##.#.....#....#.#####.#####..#..........
.#####.####..#.....#....#.#.....#......#..###.....
.#...#.#...#.#.....#....#.#.....#......#....#.....
.#...#.#...#.##....#....#.#.....#......#....#.....
.#...#.####...####.#####..#####.#......######.....
..................................................
..................................................
...#...####...####.#####..#####.######.######.....
..#.#..#...#.##....#....#.#.....#......#....#.....
..#.#..#...#.#.....#....#.#.....#......#....#.....
.#...#.#..##.#.....#....#.#####.#####..#..........
.#####.####..#.....#....#.#.....#......#..###.....
.#...#.#...#.#.....#....#.#.....#......#....#.....
.#...#.#...#.##....#....#.#.....#......#....#.....
.#...#.####...####.#####..#####.#......######.....
..................................................
..................................................
...#...####...####.#####..#####.######.######.....
..#.#..#...#.##....#....#.#.....#......#....#.....
..#.#..#...#.#.....#....#.#.....#......#....#.....
.#...#.#..##.#.....#....#.#####.#####..#..........
.#####.####..#.....#....#.#.....#......#..###.....
.#...#.#...#.#.....#....#.#.....#......#....#.....
.#...#.#...#.##....#....#.#.....#......#....#.....
.#...#.####...####.#####..#####.#......######.....
..................................................
[出力例(debug版)]
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
1 2 3 0 5 6 7 0 0 0 0 12 13 14 0 0 0 0 19 0 0 0 0 0 25 26 0 0 0 0 0 32 0 0 0 0 0 0 39 0 0 0 0 0 0 46 47 48 49 50
2 3 0 0 0 7 8 0 0 0 0 0 14 0 0 23 22 21 20 0 0 0 0 0 0 27 0 37 36 35 34 33 0 45 44 43 42 41 40 0 56 55 54 53 0 47 48 49 50 51
3 4 0 0 0 8 9 0 0 0 0 0 15 0 25 24 23 22 21 0 0 0 0 0 0 28 0 38 37 36 35 34 0 46 45 44 43 42 41 0 55 54 53 52 0 48 49 50 51 52
4 0 0 0 0 0 10 0 0 0 0 0 16 0 26 25 24 23 22 0 0 0 0 0 0 29 0 0 0 0 0 35 0 0 0 0 0 43 42 0 54 53 52 51 50 49 50 51 52 53
5 0 0 0 0 0 11 0 0 0 0 18 17 0 27 26 25 24 23 0 0 0 0 0 0 30 0 40 39 38 37 36 0 46 47 46 45 44 43 0 55 54 0 0 0 50 51 52 53 54
6 0 14 15 16 0 12 0 0 0 0 0 18 0 28 27 26 25 24 0 0 0 0 0 0 31 0 41 40 39 38 37 0 45 46 47 46 45 44 0 56 55 56 57 0 51 52 53 54 55
7 0 13 14 15 0 13 0 0 0 0 0 19 0 0 28 27 26 25 0 0 0 0 0 0 32 0 42 41 40 39 38 0 44 45 46 47 46 45 0 57 56 57 58 0 52 53 54 55 56
8 0 12 13 14 0 14 0 0 0 0 21 20 21 0 0 0 0 26 0 0 0 0 0 34 33 0 0 0 0 0 39 0 43 44 45 46 47 46 0 0 0 0 0 0 53 54 55 56 57
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
11 12 13 0 15 16 17 0 0 0 0 22 23 24 0 0 0 0 29 0 0 0 0 0 35 36 0 0 0 0 0 42 0 0 0 0 0 0 49 0 0 0 0 0 0 56 57 58 59 60
12 13 0 0 0 17 18 0 0 0 0 0 24 0 0 33 32 31 30 0 0 0 0 0 0 37 0 47 46 45 44 43 0 55 54 53 52 51 50 0 66 65 64 63 0 57 58 59 60 61
13 14 0 0 0 18 19 0 0 0 0 0 25 0 35 34 33 32 31 0 0 0 0 0 0 38 0 48 47 46 45 44 0 56 55 54 53 52 51 0 65 64 63 62 0 58 59 60 61 62
14 0 0 0 0 0 20 0 0 0 0 0 26 0 36 35 34 33 32 0 0 0 0 0 0 39 0 0 0 0 0 45 0 0 0 0 0 53 52 0 64 63 62 61 60 59 60 61 62 63
15 0 0 0 0 0 21 0 0 0 0 28 27 0 37 36 35 34 33 0 0 0 0 0 0 40 0 50 49 48 47 46 0 56 57 56 55 54 53 0 65 64 0 0 0 60 61 62 63 64
16 0 24 25 26 0 22 0 0 0 0 0 28 0 38 37 36 35 34 0 0 0 0 0 0 41 0 51 50 49 48 47 0 55 56 57 56 55 54 0 66 65 66 67 0 61 62 63 64 65
17 0 23 24 25 0 23 0 0 0 0 0 29 0 0 38 37 36 35 0 0 0 0 0 0 42 0 52 51 50 49 48 0 54 55 56 57 56 55 0 67 66 67 68 0 62 63 64 65 66
18 0 22 23 24 0 24 0 0 0 0 31 30 31 0 0 0 0 36 0 0 0 0 0 44 43 0 0 0 0 0 49 0 53 54 55 56 57 56 0 0 0 0 0 0 63 64 65 66 67
19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
21 22 23 0 25 26 27 0 0 0 0 32 33 34 0 0 0 0 39 0 0 0 0 0 45 46 0 0 0 0 0 52 0 0 0 0 0 0 59 0 0 0 0 0 0 66 67 68 69 70
22 23 0 0 0 27 28 0 0 0 0 0 34 0 0 43 42 41 40 0 0 0 0 0 0 47 0 57 56 55 54 53 0 65 64 63 62 61 60 0 76 75 74 73 0 67 68 69 70 71
23 24 0 0 0 28 29 0 0 0 0 0 35 0 45 44 43 42 41 0 0 0 0 0 0 48 0 58 57 56 55 54 0 66 65 64 63 62 61 0 75 74 73 72 0 68 69 70 71 72
24 0 0 0 0 0 30 0 0 0 0 0 36 0 46 45 44 43 42 0 0 0 0 0 0 49 0 0 0 0 0 55 0 0 0 0 0 63 62 0 74 73 72 71 70 69 70 71 72 73
25 0 0 0 0 0 31 0 0 0 0 38 37 0 47 46 45 44 43 0 0 0 0 0 0 50 0 60 59 58 57 56 0 66 67 66 65 64 63 0 75 74 0 0 0 70 71 72 73 74
26 0 34 35 36 0 32 0 0 0 0 0 38 0 48 47 46 45 44 0 0 0 0 0 0 51 0 61 60 59 58 57 0 65 66 67 66 65 64 0 76 75 76 77 0 71 72 73 74 75
27 0 33 34 35 0 33 0 0 0 0 0 39 0 0 48 47 46 45 0 0 0 0 0 0 52 0 62 61 60 59 58 0 64 65 66 67 66 65 0 77 76 77 78 0 72 73 74 75 76
28 0 32 33 34 0 34 0 0 0 0 41 40 41 0 0 0 0 46 0 0 0 0 0 54 53 0 0 0 0 0 59 0 63 64 65 66 67 66 0 0 0 0 0 0 73 74 75 76 77
29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
31 32 33 0 35 36 37 0 0 0 0 42 43 44 0 0 0 0 49 0 0 0 0 0 55 56 0 0 0 0 0 62 0 0 0 0 0 0 69 0 0 0 0 0 0 76 77 78 79 80
32 33 0 0 0 37 38 0 0 0 0 0 44 0 0 53 52 51 50 0 0 0 0 0 0 57 0 67 66 65 64 63 0 75 74 73 72 71 70 0 86 85 84 83 0 77 78 79 80 81
33 34 0 0 0 38 39 0 0 0 0 0 45 0 55 54 53 52 51 0 0 0 0 0 0 58 0 68 67 66 65 64 0 76 75 74 73 72 71 0 85 84 83 82 0 78 79 80 81 82
34 0 0 0 0 0 40 0 0 0 0 0 46 0 56 55 54 53 52 0 0 0 0 0 0 59 0 0 0 0 0 65 0 0 0 0 0 73 72 0 84 83 82 81 80 79 80 81 82 83
35 0 0 0 0 0 41 0 0 0 0 48 47 0 57 56 55 54 53 0 0 0 0 0 0 60 0 70 69 68 67 66 0 76 77 76 75 74 73 0 85 84 0 0 0 80 81 82 83 84
36 0 44 45 46 0 42 0 0 0 0 0 48 0 58 57 56 55 54 0 0 0 0 0 0 61 0 71 70 69 68 67 0 75 76 77 76 75 74 0 86 85 86 87 0 81 82 83 84 85
37 0 43 44 45 0 43 0 0 0 0 0 49 0 0 58 57 56 55 0 0 0 0 0 0 62 0 72 71 70 69 68 0 74 75 76 77 76 75 0 87 86 87 88 0 82 83 84 85 86
38 0 42 43 44 0 44 0 0 0 0 51 50 51 0 0 0 0 56 0 0 0 0 0 64 63 0 0 0 0 0 69 0 73 74 75 76 77 76 0 0 0 0 0 0 83 84 85 86 87
39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
41 42 43 0 45 46 47 0 0 0 0 52 53 54 0 0 0 0 59 0 0 0 0 0 65 66 0 0 0 0 0 72 0 0 0 0 0 0 79 0 0 0 0 0 0 86 87 88 89 90
42 43 0 0 0 47 48 0 0 0 0 0 54 0 0 63 62 61 60 0 0 0 0 0 0 67 0 77 76 75 74 73 0 85 84 83 82 81 80 0 96 95 94 93 0 87 88 89 90 91
43 44 0 0 0 48 49 0 0 0 0 0 55 0 65 64 63 62 61 0 0 0 0 0 0 68 0 78 77 76 75 74 0 86 85 84 83 82 81 0 95 94 93 92 0 88 89 90 91 92
44 0 0 0 0 0 50 0 0 0 0 0 56 0 66 65 64 63 62 0 0 0 0 0 0 69 0 0 0 0 0 75 0 0 0 0 0 83 82 0 94 93 92 91 90 89 90 91 92 93
45 0 0 0 0 0 51 0 0 0 0 58 57 0 67 66 65 64 63 0 0 0 0 0 0 70 0 80 79 78 77 76 0 86 87 86 85 84 83 0 95 94 0 0 0 90 91 92 93 94
46 0 54 55 56 0 52 0 0 0 0 0 58 0 68 67 66 65 64 0 0 0 0 0 0 71 0 81 80 79 78 77 0 85 86 87 86 85 84 0 96 95 96 97 0 91 92 93 94 95
47 0 53 54 55 0 53 0 0 0 0 0 59 0 0 68 67 66 65 0 0 0 0 0 0 72 0 82 81 80 79 78 0 84 85 86 87 86 85 0 97 96 97 98 0 92 93 94 95 96
48 0 52 53 54 0 54 0 0 0 0 61 60 61 0 0 0 0 66 0 0 0 0 0 74 73 0 0 0 0 0 79 0 83 84 85 86 87 86 0 0 0 0 0 0 93 94 95 96 97
49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
1696