Eternal Truths

Problem Number: 
928
Type of Problem: 
Single Output Problem
Problem Category: 
Volume 9 (900-999)
Input: 
Random Input
0
0
Critical Input: 
Random Input: 
100 11 14 .#####..#..#.. #....####..... ##.......##.## #..#..##.#..## ....#.#.#####. .#..###..#.### ##..####.#.##. #.#.....#.#..S #.###..##.#... .##....####E.# ####..#.#..##. 15 15 .###.##......#. #..#.#.##.#.... ##.###.#.#...#. #.#....#....#.. ....##..#..#### .#...###.#.#... #..##.#.###.##. ...###..##..### #.....#..#...## #....S.#..###.# #..###.#.##.#.. #.#.#...#E####. .#####.#####.#. #######..##.##. #.####..#...#.. 8 6 ##.##E .#S.#. ....## #.#... #.##.# #.##.# ....#. ..#### 3 13 #####......## #.S#.#.#.E..# ........#...# 10 20 #.#.#.#.#.#.###..### ##..#..#####.#....#. #.#...##..#..##..... ......###.#.###..#.# ...#..E...##.#.#.#.. ..#..##....##..##... #.#...##..####....## ###.....##....#.##.S ..#.##.....#...#.##. #.#.#.##.##...#...## 21 19 .#....##.#..##....# ##....###...#....#. ...#..####.###....# ....#.#.#.#.#.###.. .#.##.###..#.#.#### ####.#...#.#.....## .#.#.####.........# ###.#.#..#..E###..# ...####....#..#.##. ....#..#.#.....#..# ...#.#.......####.. .#.###..#.###..###. #...###.###...##.#. #.##.##.##.###.#..# #.####.####.#.#..#. #....#.###.####.### ##.##.###.#....##.. #.#..#....##.#.#### #...###.#.#.....### #.##..##..S..#####. #####.#.##..#..###. 13 3 ### ##. #.. ..# .#. .#S #.. #.. .#E .#. .#. ... #.# 2 21 ##....#...##...E##.## ##.S#.##..###..#.#.#. 4 9 ...#...#. #..#S.#.# ..####..# .E###..#. 6 18 ##..###..#..#S#.#. .#..#.#.#..##.#..E ..##....#.#####..# #...#..###..#####. #..#..#..#.#...### .#####.###....##.. 5 20 ##...#.##########... ##E..###.##.##..#### ######S############. #....##.##.......##. .##.##.###...#####.. 7 19 .##.#..#E.##.##.... ..#S#..#...##.##... .#..####.....#..### #.....##.#....#..#. .###..#######...#.# ####....#.#.###.... .##.######.#..#...# 5 12 #....##.#... ...##..#.#.# #.#####S..## .#.##...##.. .#.#E##..... 14 14 ..##.#.####... ##.###...#.#.. #.....###..#.. .#..E####.#.#. ..##...##.##.. ##.#.#..#.#..# #.S##.#.#..#.# .#..##..#...#. #..####..##.## ..##..#.#..### ....###.###..# #.#.###.####.. ##.#.#..#.#### ....#..##..#.. 14 4 #..# .... #.#. #..# #S## ..## .### ..#. #... .... #.#E #..# .#.# ..## 4 21 ####S...#.#.#######.# ...#.####.#####...#.E .....#...#.#........# ..####.#...##.###.### 12 21 ..#...#..###...S##.#. .#.......##.###.#.##. #..##.##...#.#.#.#..# #.####..#...#.#.###.. ##..#..######.#.#.... ..#.##..##.#...##..#. ..#.#...#####.#.#..#. .#####....##.###....# ....##..##.##..#.#.#. ....##....###..###.#. .#.#E#.####.....###.# ###.###.....#.###.##. 12 11 ####.###..# ###..#.#... .##..#.#S.# #..###..##. #.#.####..# E..##...#.# .##...#.##. .........## .####.#..#. #....###... .#.#.####.# #.#.####.#. 20 15 #.#...#..#..... #####.#..##.... #.##.##....#.#. ##....#......## ##...#...####.# .#...##...#.#.. ####..######### ..###.#.#.###.# #.#E...#..#..#. ..#...#.##.#... .....####..##.. .##.###S.#.#.## #...#.##.#....# ####.###.####.# ##.#.....###... ...#.####.#..## ..##.#.#.##.### ...#...#....#.. .##....#...##.# ...#...#.###.#. 19 17 .#.#.##E##..#.#.. .#..#..##.#.#.### .#..#.#.####..... #.##.#....#S....# #..##.#...#.#..#. ...#......######. .##..#.#...#..#.# ##.#.#.##.#..#### ..##..#.#.####### ###.#..######..#. #..##..#.#..#.##. .###.#..#.##.##.. #.#.#...#####.#.# ###....#.##...... #.######.#......# ...#.##..###..##. ##.###...#..#.#.# ####..#...#...#.# #....###.#....... 17 7 #.#.##. #.#.#.# #.S##.. .###### ....### ##...## #.##.#. ..#.... #.#...# ..####. .#...## ##.#... E#####. .#.#.## .#..#.# ..##..# #..#... 18 2 .. #. .# .# ## #. S. .# #. #. ## .# .# ## E# ## .# .# 6 19 ..#..##.#.#......#. .##.#..#...#.##S#.# ....##...#####..##. ..###.##.#.###..### #..##.#.#...#####.# ...#...##.#..E#.#.# 5 19 #...#S#.###...#...# ..#.###..###...#### ..####.#.#..##E.#.# #####.#..##...#..## #...#.####.###..##. 15 20 ..##.###.#.##..##..# ##.....#.######...## ....##.#.#.###...#.# #######..###.......# .####......#..#.##.. #.#.#.#.##.####...#. ##......##.#..#.###. #.....#.###.#.###..# .#.#...#...#.#.#.... ..###.#.#..####..#.. .#.###...#.##.####.. #..E......#....#.#.# .##.#..#....##..#.#. ###.S#.##.#...#.###. ....####.....#..##.# 15 18 #.###.#.###.#.#... .##.######..#.#.## ###.####.E.#..###. ##.###....#..#.... ........##.#...#.. ###..#.#.####.#.#. #####...##.....### #...#.####...#.##. ..##....#..#..##.# ..##...#.###.#..#. #.###.####S.#####. #.#..#.##..##.##.# ..#.#..#......#.#. .#.#.##..#.#.#.... ###.#.#.####..##.. 20 11 ......#..#. ...#.###.## #.##.####.. .###.##.... ########.## .#..#..#..# ......#.#S. #....##.#.# .##.###...# #.#....#### .......#..# .####...#.# #.#.##.#E#. ###..###..# ..#.##.##.. ##...#..... ##.##..##.. ####.#.#..# ##.####.### .######.#.. 8 16 .##.#.##.E#.#### #.#..S.##.##.### ##........#...## ##..####.#.##.#. #.#...##..###### #..#...#.###.#.. #...#...#.##.### ###...#..#...##. 17 13 ....##.##.#.. ##..#.#.##... ..##...##.### ..#####..#... ....###.#.#.. ..#...#...#.# .#....###.### ####....###.. .S..#..###.#. .....#.##...# #...##.#...#. ..#.#....#.## ..####...#.## .....##..#.## #..#..#..#... #.##..##..#.# .#.#E...##### 11 12 #.#..#.#...# #..#.....#.. #...##.#.#.# ####.###..#. ###.#.#S.... ..#.....##.. #....##.##.# #.#...####.. #..#.#..#.#. ..#.E.....## #.#..##....# 4 15 ..#.##...#####. #.####.....#E.# ##.#S.#.##.##.. ..#.##..#...... 12 9 .##.#.### ..#..###. #.#..##.. ##...##.# ...####.. #.#...#.# #....#... ..#.#.##. .S.###### ##.####.# ##...##.E ....#.#.# 3 16 .####.###.....E. .######.##.#.### ####.##.S#.#..## 2 8 .#E###.# #.#.##.S 19 4 #.#. #..# ...# ..## #.## ###. ###. ##.# ..#. #.## #.## #.## #S.# E... .### #.#. ##.. #..# #.## 3 14 ##.#..#..##..# ##.#.##.#.#S#. .....#.#E..#.. 17 3 #.# ### .## ... .#. #S# .## #.. #.# #.# ... E.. ..# ##. ..# ##. ... 5 5 ..#.. .##.. ##.## S.#.# #E... 18 19 ..###.#.##.#...##.. #...#..#.###.###### .###.#.###.###.###. #...#..#..#...#.##. ##..#..#..#..##E#.. ##..####.#####....# .#...#.#...###..#.. #..#..#.#.####.##.. ##.....##.#...#.#.# .....#####..###.... ..#.####....##.#..# ..#.##...###.#..#.. .####....##.#.....# ###....#S..##.#...# ####.#.#.....#.#... ...#...##..#.#.#... #.#.##.###.#.#..##. #.#....#..#....#..# 2 6 ....S# .E#### 8 14 #.#S..##E....# ##.#.##.##.#.. ......##.###.. ##.#.####..... .##.#.#..#.#.. ##.#.#.#..#.#. ######.##...## ..#...##..#### 21 18 #...#...#.#.###..# ##.#.#...E.#.#.#.. .#....#....#..#... .###.##.#.....###. ...###S..####..#.# #..#..######...#.. #.....#...##.##... #..#..####....##.. #...#.....####..## #..#.#.#...#...##. ...#....##.#...### #....###..#...##.. .#...###..#.##...# ..##.#.#..##...#.# #.#.##.###..##.### #.#..#.#.#####.#.# #########.#..##... ...#...#.##.#....# ..#.#.#...#.#.###. .....###...#.###.# .###.#..#..#...### 7 21 #..#..##.###.#.....## #.##.#...#.##.....### #.#.#.#.##..#.###.#.# #..##..#..##..#.#..## #..#.##..#S####..E#.# ##.#...##.#.#.##.#..# ..#.#..##.#..###..##. 17 13 #..#####....# .#.##.###.### .##.###.##.## #####.#.E##.# .#...#....#.# ###.##.##..## #.##..###.S#. #..##.#####.. .##.#.#..##.# ....###.##### .#.#.#.#...## ##..####.##.. #####.#..#.## .#..#...#.... #..#..#..#### .#.####..#### ##...#..####. 16 8 ######.# ..#..##. ###.##E# ...#..#. ...#.### .#...##. #S#.#... .#.##.#. #..##.#. ###.#### ##.#...# .#..#..# #####.## .#...... ..###... ##.#.##. 10 6 #.#.#. #...#. ###.## ..#E.. ..#.## .#.##. .###S. .#.#.. ###.#. #..#.. 12 5 ##### #.##. #.##. ...#. #...# .#S## .##.. ..#.. .E##. ...#. #..## ..#.# 8 17 ###...##.#.#.##.. ...#.##....#.S... #.#..#.#####..... ##.#.#.###..###.. .#.##.#.#.#.#..## ..###...#.###..## .#.....#...####.# #....##.######.E. 6 8 .##.##.# .###.#E# S.#####. #....#.# #.###.#. .#..##.. 18 13 .###..####### #...#.#.#.... .#..#####.#.# #.####.E..#.. ###...####### .#####.##.#.# ...##..#.#... ..S#.######## ..###.....##. ..####..#.##. ##.#####.#.#. ##....##.##.. ##.#.#####.## ##.#..#.##### .######.#..## ##.##....###. .#..#.##.###. #..#..##.#.#. 6 12 .##..#.##.#E .##....#.... ###...##.#.# ####...#.#.# S###.##.##.# ..##.##.#..# 10 18 .#######.#.###...# ....##.#.#..#..#.# #.##..####..####.. #.......##..###.#. ##.E##S.##.#...#.# .#..###.######.... #####.#...##..##.# ....#.###...#...## ##..#.....###...#. .#....###..#...... 4 6 E#...# ####.# ..S... ###... 13 20 ..###.###.#......##. #########.#.####.#.. ...#.#.##..##.##.##. ##.##....#...#.##.## #.###.#..#..####..## ...#....#..#....#..# ##.##...#...#.#E#.## #.#.#....#..##.###.# .##..##..#...#.#.#.# ##.##.##......#...## .#..##..#####.####.# .#....######S..##### ##.#..###.#...#####. 18 12 #######.#..# ..#.#.#.#..# ##..#..#..#. .#...#....#. ..#.##.###.# .###.####..# .#.##...#### #.##S.....## ####..###.## ......#.#### #.#.######.. #..#..###..# #..##..##... ....#####.#. ##.#.##.##.# E###...#.#.. ....#.##...# .....#.....# 14 8 ..####.# .#.##.S. #..###.. .#.##.#. .#...### #.###... #..#.#.# .##.#... .###.##. #####..# ##.#.### ..E.###. .###.#.. ........ 9 12 ##.#..#.#..# .#...##...## ...######.#. #.#.#..###.. #.#..####.## ..#.#E#.#### ..#.#..#..## ####.###.#.S ......###### 14 3 .S. .## .## ... .## ##. .#. .#. ### ... ##. ..# ..E .#. 5 14 .###.##..###.# ...#.#......#. ...#......##.. ...##.#E.##... ####..S.#.#### 21 11 ..###.###.# ..#..#.##.# #.#..###.#. .#.###..##. #.####..#.. ####....##. #..#####.#. ....#...### ##..####.#. ##.##.###.. #...#..#.S. #..#....... #..#..#..## #.#.#.####. .###...#### .#.###..### ...##.###.. #.#......#. ##..##.E.#. ##..##..... .###....##. 2 11 .....####.. E##S##....# 16 15 .###....#..#### #..#.#....###.# .#S###E...####. ###.#...#.#...# ##..#..#......# #.###.####...## ###...#...##..# .#..#####...##. ####...###.#.## ..##.##..###.## .#...####..#.## ..#...###.#..#. ..###..#...#..# ##.##..#....##. #.####...###.#. .##.###.#.#.#.. 17 18 .S.####.##.######. #....##..###..##.. #.##..#..#....#.## .#.....####......# .####.##.#..####.. ...#...###.#.##..# #.#....##.#.#.#... #......#...#.#.#.. .#......#.##...##E ....##..#..##.#.## #..#.###..#.###..# .#.#..#.########.. #.....#..####....# #.####.#..####...# #..#..#....##.#### #.#.#..#......#..# ##...##.##.###.#.. 12 18 #..##.#..#######S. ##....###..#....## ##..#...#..#.#.#.# .##..#....#..###.# .#..#.#....#..#.## .#....##.###..##.# ...##...#.##.###.. ...##.#....#...... #######.#E#.#..##. .###..#.#.######## .##..#.#.##...#.#. ###.##.##..###.#.# 8 8 ..#.###. #.##...# #####.#. ######.. #.##.#.. ..#.#SE. .....##. ##.#.#.. 20 13 #.###...##... #...####..### ....#.....##. ###..#.#..#.. .#.S...##...# #.#######.#.. .###.....#### #..##..#..... .#.#.##.#...# #.##...#...## #...##..#..## ....#.##.#..# ######..#...# .#.....##.##. .#.#....#.... ..#..#...###. #..#.#.#.#.#. ..#.###....## #.#E###....#. ##.#.##..#... 5 9 ######..# #E...#.#. .###.#.#. #.#..#... .##.S#... 14 2 .# .. #. ## ## .. .# ## .# #. SE ## #. .# 14 13 ##.##.#...... .###.##E#..#. .##.###.###.# .#..##.#S###. .##...##.##.. ...#..#.##..# #..####..##.# ..###.##...## .###.#.##.#.# .....##...... ####.....#.## ..###...##..# ##....#.#.#.# .....##..###. 19 11 ##....#.### #...#S.#.#. #.#.#...... ###.##.##.. ##.#..#E##. ...###..... .#....##### .#####.#.#. ##.###...## ##..##.#### #..##..#..# #.#.###.#.. .#..#.##.#. #..##..##.. ####..##### ..##...###. ##.....#.#. .###.##.#.# ..######.## 19 12 ...##.#..##. .#######.... .#..#...##.# ...#...##### ##...#.S#### ...#.###.##E ..#..###...# .#.#..#####. #..#..##..## .###.#.####. #.##.##....# .#.#..##...# .##.#..##... ..#.##..##.. .#.#.####... ##.#.#....## ....#.#..### ###...#.#... ###.##..#..# 7 17 .##...#..#####.## ...#.#..#.#.##### ...####..#.#...#. E...####.###.#.## ..###.#....#.###. .#.......###.#### ####..###.####.#S 15 11 #.#..#..#.. ##.#..#..#. ##.##.S...# .#...#.##.. .####..#..# #.#.#.##..# ###..#...#. .#....##.#. #...#...#.# ##.#.##.... ###.##.#..# .E##..#..#. .....#.##.. #...###.#.. ##..##...## 16 21 .##..#E.#.###.###..## ######..####.#..##..# .##.###.........#.S.. ##.#.###.....##.#.#.. ..#.#.###..#......### #.##.#..##...#.####.. ###...#####.####.###. ........##..###.##.## .##.##..###...###..## ######..#.######..### ....###.##..#..#####. ##.#######.#.##.#.### .#.######.#####.##.#. .#....#..##.##.#..##. #..####.#..####...#.# ..##....##.......###. 17 17 #.######.#..#.#.. ###.####.##.#.... .#.##.####.#.##.. #..#.##.###.##.#. .##.##.#.##....#. .#.#..##.####...# #.#....#.#.###### ##.###.##...#..#S #....#...#..#..#. .#.#####.#..#..#. ...#####...#.#### #####..##..#.#..# ..##.#..##.##.... ...#..#....##E### #.#.##.#.#.#...## ##.#...#.##.##..# #####.#...#..#..# 21 2 #. ## .. #. ## .# #. #. #S #. ## ## #. #. #. ## ## .. .E #. .# 2 21 ##.S.............#.#. .##...#.##.#.#.#....E 19 16 #######.###.#### ..#.#......#..## .##..#..#.##.#.# ...###..#...#... ...###.#...####. ....#.###..##... #####....#..#.#. .##..#...#...### .##.#....##.###. ###.#.#..E#.#... ..#...######.#.. ....#.....#.#.## .#S########....# ##.#.#.###.#..## #####.##.###..#. .#.###.###.##.## ..#.###.###..### #.#....########. .#..#..#...#..## 12 10 .#..#.###. #..####... .##.###..# #.#.###### ###.##.### ..#.....## .#...#..#. ##.#..##.# ###...#### #..####.S# ##..####.. ....E##### 2 19 ####.###.##...##... ...#S...#.#..#.#..E 15 16 ..###.#.###....# .#.#...##.#....# S..##..#...##### #.#.....#.#.#.## #.###.#.#..#..#. ###.#.######.##. .#....#.#...#### ####.#.....#..## ...#....#..#..#. ###....####.##.. ###...#.#....... #.#.#..##..###.# #.....#....###.# .....#..##.##### #...#.#.#E.#.#.# 13 20 #.#..#..#.#.###.###. .#######..#.#.#...## .#...##.#.#..#..##.. .###.#.####.###.#S## #.#...##.#..##..##.# ##..####..#.###.##.. #.##....#.##.....#.# ....#.####.#.#.#.#.. ..##...#.#.###.##### #.#.....###.###.#... ####..#..E....#...#. ####.#..####.#####.. ##....##.#...#.###.# 12 8 .###.### #####..# ###.##.. ..#..### #E.#..#. .#.#.##. #####... .#.##.#. ...#...# #.#..#.# #.#.S### #.####.# 14 12 .#.#.####.#. #..#..#..#.. #...#..#.##. ##....#.#.#. ###E###..### ..#..##.#.## .#.........# ........#.#. .##....#..#. #.###.##...S ##.#...#.... #..##..##.#. .#.#.##.##.. .#..####..#. 5 16 ##E.##.##.#.###. .##.#.#...#..... .#...##.#######. ###.S.####..#... .#.##..#.#.##... 21 20 ..##.#.##.#..##....# ....##.####...##..#. ####.#.####...##..#. ....#...##..#...##.# #...##...#...##...#. ..##........##..#### #.....###.#####.#.#. #...#######.#.#.#.#. ##.##.#####.#.##.##. #.###.#.#####.####.# ....#.....###.#.#### ####.#...#.#....#### .###.#........###... .#.#.E.##.#..#..###. .#.#..#.#.#.#....#.. ...#.#.#.#.###...... ..#...##.###.....#.# S#.#.###..####..###. ###...##...####.##.. ..###..#.......##..# .##.####...#..#..#.# 20 3 .## ##. ### #.# ### ##. ..# #.. .#. ... #.# #.# ##. #E# ..# ..# ##. #.# .S. #.# 7 5 #...# ...#. #.### .S.#E ...#. ....# ###.. 17 6 E##.## ..###. .##... ##.### ##...# .###.. ####S. ....#. ...#.. ...### #####. .#.##. ..###. ..###. ...#.. #..#.. ...#.. 12 19 .##.####..##...#..# .#.........##...#.. #..#.#..#.#####...# ##.....##..#.#..#.. ..#.##.#.#.##...#.# #..#.#####.....#.E. .#.##..#.#..##.##.. #..##....##...#..## ..###......#.##...# ###...###.#......#S .#.##.###...##..... ..#.#.##.##..#...#. 5 15 E.###.#...#.### ##...####...##S ....#.##.#..... ...###.##.##### .###.####.#.#.. 20 5 ..... ...## ###.. #..## ..### S#... ###.# ..... ....# #..#. ....# .#### .#### #..## #.#.. #.##. #.E.. .#... ...#. .#### 15 5 ....# ...## #..## ....# ..#.# .###S .###. .#### #..#. ..#.# ##.#. .#..E .##.. ##.#. ..#.. 9 18 .......###..#.##.. .####...#.#....#.# .#####.....###.##. #..##....####.#... .###..#.#.##.##### ..######....##.##. ..S.###.##.##.##.# ####.#..E#...##### ###.#..##..#..##.. 7 7 .#..#.# ..##... ##.E### ###.##. ..###S# #.#.##. #..#.#. 21 13 #.#.#......## ..#..######.. #...#..#..### .....#.#.#### .###.#.####.# .##..#.#.#.## ##.#######.## .####.#....## ##.....###### ##.#.##.#...# ##.##.#.#..#. .#..#####.#.# .#.##.#...### .....#.##.##. ..##..#..##.. ##.#.#.#.#.#. .#...##.#.### E#..S....#.#. ..#.#...#.### #...##....#.# ....######..# 5 18 .#..#.####.#.#.#.# ..#....##.#.#...#. ##.####..#.###.S## ......E.#.##..##.# .#.#####..#.#.#... 15 11 #E###.#.... ....#.....# ##.#.###.## .#.####.#.# ...###..#.. #..#....##. .#..##.#... #..#...##.# ....#..#### #..#...##.. .###...#.#. #...#.##.## ##..#...#.. ..####S...# #.......... 10 9 S.#...... ##....##. ..##..#.# ...#.#.#. #.....### #.#.##... #.#.#.#.# #####...# ##.E##..# .#.###... 14 18 .##......##.###..# ##...##.########.. .##...#...##..###. .#..#..#..###..### ...###....S....##. ....#..####.###### #.....###.###...#. ##.###..#..#..#.#. ##......#.#.##.##. ####..#.####.###.. ..####.####..#.### ...#..#.#...#.#..# .#.##...##.##..#.. ..#.#.E.#.#.#.....
Problem Description Link: 
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=1…
Problem Id: 
928