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
mastik5h_1998: 2017-09-22 03:08:38

easy top-down

kartiks22: 2017-08-05 09:51:25

ac in 1 go :)

anurag44: 2017-06-16 23:13:31

easy [spoiler] !!

Last edit: 2017-08-02 13:11:04
da_201501181: 2017-06-06 08:29:12

Nice Question [spoiler] Works..!!

Last edit: 2017-08-02 13:11:15
krototype: 2017-05-26 05:21:20

Take care....starting index can also have '#'

Nafis Islam: 2017-05-24 14:51:35

[spoiler] + [spoiler] = ac :D

Last edit: 2017-08-02 13:11:28
kshubham02: 2017-04-17 08:42:17

Thanks @Ruchir Thaman
If the box 0,0 is blue (#), your answer should be 0.
Also, what is the point of removing spoilers from comments when the tag gives it away?

gautam: 2017-02-25 06:03:50

nice one..:)

akshayvenkat: 2017-01-16 20:58:41

Finally solved it. :-D Thank you @cegprakash senior!
[Spoiler]-> TLE
Plain [Spoiler] -> AC!
Great problem.

Last edit: 2017-01-17 04:01:09
kira28: 2016-12-28 20:29:19

Finally AC !!! :)
Nice problem for [spoiler] beginners

Last edit: 2016-12-28 21:08:32

Added by:cegprakash
Date:2012-10-14
Time limit:0.346s
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