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:


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

hide comments
2021-02-01 10:09:17
creative problem
must try
2020-09-24 06:44:49
[spoiler] is the best AC in 1 go!!

Last edit: 2021-01-27 14:45:22
2020-08-16 18:42:20
@surajxd good

Last edit: 2022-07-24 01:58:35
2020-08-15 09:46:05
just make a [spoiler]

Last edit: 2021-01-27 14:45:40
2020-07-30 00:52:32
AC in 10 tries!!!!!!
2020-06-25 10:52:11
AC in 69th go, yet again.
floor gang aaaaooohhhh.
2020-05-12 11:48:50
for those with [spoiler] ... make sure to check ur code for even rows too.
IP
1
4 5
0TTTT
T#T#0
#TT#T
T00T0

OP : 7

Last edit: 2021-01-27 14:59:58
2020-04-15 14:19:24
AC in one go :)
2020-01-25 10:50:08
ac in 1go
2019-12-07 19:16:35
IMHO, I believe if you're handling the starting index having '#' separately, you aren't writing code the way it should be.

Last edit: 2019-12-07 19:17:14
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.