InterNAV

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Python 3 2.5s
Memory limit: 128M

Authors:
Problem type

Henry Two had been working on a GPS system for the school itself, and after years of hard work, he realizes that what he had been making already exists. Therefore, he needs to make his better. Given an m by n grid, where each position is either a numbered room, an empty space, or a wall, determine which rooms Henry can go to. Henry starts at room 1 and can only move up, down, left, or right.

Input Specification

The first line will contain the integer m, representing the width of the room (2 < m < 1\,000).
The second line will contain the integer n, representing the height of the room (2 < n < 1\,000).
The next n lines will each contain m characters, where # represents a wall, O represents an empty space, and a number will represent a room. There will be no more than 9 rooms.

Output Specification

Output the list of room numbers Henry is able to travel to (including room 1), separated by spaces and sorted in ascending order.

Sample Input 1

5
4
O3OO2
OOOO#
1###4
#5OOO

Sample Output 1

1 2 3

Sample Input 2

7
8
OOO#2O#
1OOOO#3
OOOOOO#
OOO7OOO
OOOOOOO
##OOO#O
O4#O#5O
6O#OOOO

Sample Output 2

1 2 5 7

Comments

There are no comments at the moment.