MAXWOODS - MAXIMUM WOOD CUTTER


Problem Statement:


The image explains it all. You initially step at 0,0 facing right. At each step you can move according to the conditions specified in the image. You cannot step into the blocked boxes (in blue). Find the maximum number of trees you can cut.

Input:

The first line consists of an integer t, the number of test cases. For each test case the first line consists of two integers m and n, the number of rows and columns. Then follows the description of the matrix M.

M[i][j]=’T’ if the region has a tree.

M[i][j]=’#’ if the region is blocked.

M[i][j]=’0’ (zero) otherwise.

Output:

For each test case find the maximum trees that you can cut.

Input Constraints:

1<=t<=10

1<=m,n<=200

Example:

Sample Input:

4
5 5
0TTTT
T#T#0
#TT#T
T00T0
T0#T0
1 1
T
3 3
T#T
TTT
T#T
1 1
#

Sample Output:

8
1
3
0

Solution for test case #1:


hide comments
Niklas Baumstark: 2014-04-17 09:55:41

I think the problem statement is a bit ambiguous: You say that "You cannot step into the blocked boxes", when in fact you can also not step *out of* a blocked box. The correct answer for the test case

1
1 2
#1

is therefore 0, not 1

Sardar Khan: 2014-04-17 09:55:41

simple graph problem

Reply : not necessarily

Last edit: 2012-11-07 15:39:30
Rocker3011: 2014-04-17 09:55:41

we always start facing right?

Reply : Yes

Last edit: 2012-11-04 02:26:59
ramaravind: 2014-04-17 09:55:41

nice prob..:)

bashrc is back: 2014-04-17 09:55:41

There are test cases where (0,0)='#'

(Tjandra Satria Gunawan)(曾毅昆): 2014-04-17 09:55:41

this is strange, my optimized code is slower than my first ordinary code... :-/
RE: happens bro! :P

Last edit: 2012-12-29 19:01:32
Francky: 2014-04-17 09:55:41

@cegprakash : I don't understand why I got WA, could you check my Python output, please ?
Edit : AC, the trick for me was : we do not have to go until the last line, best can be done before.

Last edit: 2012-10-21 20:52:10
ɥsǝןǝǝu: 2014-04-17 09:55:41

TLE again and again......
AC after a long time......nice question

Last edit: 2013-01-28 18:06:43
Archit Mittal: 2014-04-17 09:55:41

can somebody give a tricky test case as i am getting WA after 5th judge
EDIT:Got AC

Last edit: 2012-10-22 14:39:05
:D: 2014-04-17 09:55:41

Nice work on the images. Could you put them on SPOJ, since missing images are a plague here. Pictures from places like dropbox will evaporate sooner or later.

See here for an example:
http://www.spoj.pl/problems/BABTWR/

If you have problems with submitting images to SPOJ, please contact me via e-mail and will sort it out.

Last edit: 2012-10-18 21:12:49

Added by:cegprakash
Date:2012-10-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Inspired from http://codeforces.com/problemset/problem/115/B