What is the Problem?
Sanjay and his friends are searching for treasure in an abandoned castle. They have just entered the castle and find themselves faced with a maze of treasure-filled rooms separated by locked doors. Fortunately for them, the old owners left spare keys littered around the castle.
Sanjay finds that they can use any key to help open any door in the castle. However, some doors require multiple keys in order to open them.
The floor plan of the castle can be represented as an N x N grid of the following characters:
‘.’ denotes an empty space
‘#’ denotes a wall.
Characters ‘1’ through ‘9’ denote a doors, with the number representing how many keys it takes to open the door.
‘K’ represents a key.
‘T’ represents treasure.
‘S’ represents Sanjay’s start point.
Input Specifications
DATA21.txt (DATA22.txt for the second try) will contain 10 test cases. Each test case starts with an integer N (1 ≤ N ≤ 1000). The next N lines each contain N characters denoting the floor plan of the castle.
Output Specifications
For each test case, your program should output the number of treasures that Sanjay and his friends will be able to retrieve.
Sample Input (2 cases shown)
3
.SK
#1#
T..
5
S.2.T
.K##3
11##T
....#
..T.K
Sample Output
1
2