SHOP - Shopping

no tags 

Crowd in the supermarketThe old tube screen to your computer turned out to be the cause of your chronic headaches. You therefore decide to buy one of these new flat TFT monitors. At the entrance of the computer shop you see that it is quite full with customers.

In fact, the shop is rather packed with customers and moving inside involves a certain amount of elbowing. Since you want to return home quickly to complete your half finished SPOJ tasks, you want to sidestep the crowd as much as possible. You examine the situation somewhat closer and realise that the crowding is less in some parts of the shop. Thus, there is reason for hope that you can reach your goal in due time, provided that you take the shortest way. But which way is the shortest way?

You sketch the situation on a piece of paper but even so, it is still a tricky affair. You take out your notebook from your pocket and start to write a program which will find the shortest way for you.

Input

The first line of the input specifies the width w and height h of the shop. Neither dimension exceeds 25.

The following h lines contain w characters each. A letter X symbolises a shelf, the letter S marks your starting position, and the letter D marks the destination (i.e. the square in front of the monitors). All free squares are marked with a digit from 1 to 9, meaning the number of seconds needed to pass this square.

There are many test cases separated by an empty line. Input terminates with width and height equal 0 0.

Output

Your program is to output the minimum number of seconds needed to reach to destination square. Each test case in a separate line. Movements can only be vertical and horizontal. Of course, all movements must take place inside the grid. There will always be a way to reach the destination.

Example

Sample input:
4 3
X1S3
42X4
X1D2

5 5
S5213
2X2X5
51248
4X4X2
1445D

0 0

Sample output:
4
23

hide comments
manishjoshi394: 2018-11-04 19:11:56

Used Dijkstra, got AC in one go! :D

saurabhrathi12: 2017-09-26 13:09:26

In Dijkstras, stop when you find destination, else TLE!!

amit_ranjan: 2017-08-18 22:59:06

in first test case m=4 or m=3??

Last edit: 2017-08-18 22:59:27
anurag_tangri: 2017-04-20 21:35:12

AWESOME problem learnt 10x implementation skills

akshaydeep_06: 2017-02-09 11:25:05

Simple dijkshtra problem tle with bfs

bich_luan19: 2017-01-03 08:28:56

I don't standard input implement in java. Could you help me, please?
I'm using :
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
N = sc.nextInt();
M = sc.nextInt();
if (M > 0 && N > 0) {



Tarun Jindal: 2017-01-02 05:44:25

I am also getting TLE using DFS .. : (

Last edit: 2017-01-02 05:44:54
yashwanth_58: 2016-09-23 09:39:27

Getting TLE with DFS !!!

vaibhav goyal: 2016-08-20 00:12:03

simply bfs just carefully apply each constraint carefully...
got ac after debugging a small mistake :)

trinhanh13206: 2016-08-01 06:30:04

easy BFS


Added by:MichaƂ Czuczman
Date:2004-07-01
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Swiss Olympiad in Informatics 2004