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
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