TUTBFS - Tutorial BFS

no tags 

Given a grid made of '.' and '#', you begin at (0, 0) the top left corner. It is guaranteed that (0, 0) will be a '.' The grid is n x m, with 4 <= n, m <= 100. You can move up/down/left/right/all_diagonals, with a move cost of 1. What is the furthest distance that you can reach from (0, 0) ?

Input

Given T, the number of test cases. Following this are T data sets, with the first line stating N and M. Following this are N strings consisting of '.' and '#', each containing M characters.

Output

T lines containing the maximum distance from the starting location (0, 0) in each test case.

Example

Input:
2
4 4
.#.#
.#..
.##.
....
3 9
.#...#...
.#.#.#.#.
...#...#.


Output:
7
10

hide comments
nadstratosfer: 2018-06-21 07:32:58

Statement is worded poorly, what we need to output is the maximum cost of reaching any of the reachable cells in the grid. In the first example, the cost of 7 is needed to reach cell (0, 2) (in this problem we can move diagonally also).

Constraints are stated correctly, got AC with a solution designed to crash if any of grid dimensions exceeded 100.

Even though it's possible to AC with Python, I'm downvoting this one because of stupid time limit, especially since this is a tutorial problem.

Last edit: 2018-06-21 07:37:14
olympian_: 2016-03-15 11:03:30

I dont get the fact that I get correct answer for these test cases on my terminal but get SIGSEV fault on SPOJ, any idea why?

EDIT:
Same solution got AC on making array sizes 1000*1000, initially i thought it was limited to 4*100 max, but seems like thats not properly given in the question

Last edit: 2016-03-15 11:12:17
siddiboy: 2016-03-09 20:29:04

can someone plz give me another test case... I can't figure out where m going wrong

Matthew Bregg: 2015-02-20 01:22:49

You need to find the furthest shortest distance to a point.

Stupid Dog: 2015-02-18 09:04:08

I need explain the example test


Added by:Alex Anderson
Date:2013-02-12
Time limit:0.259s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Life