## 11561 - Getting Gold

Moderator: Board moderators

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 11561 - Getting Gold

Thank you brother i found my mistake.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 11561 - Getting Gold

use flood fill,just dont dont call flood() from risky places.

outsbook
New poster
Posts: 26
Joined: Fri Oct 28, 2011 2:42 am

### 11561 - Getting Gold

1. Every T send a draft his top, bottom, left, right.
2. Find draft position for every T.
3. Start BFS from position P.
4. Find adj (left, right, top, bottom) and push to Queue when the
position is not draft ( If the position is draft then do not find adj
and do not push to Queue)
5. Count gold when run BFS.
6. If P is in position a draft then output 0. see the last input and output.
"Learning to love yourself is the greatest love of all" - Michael Masser and Linda Creed

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 11561 - Getting Gold

cut>>>>>>>>>
Last edited by mahade hasan on Sat Sep 15, 2012 4:27 pm, edited 1 time in total.
we r surrounded by happiness
need eyes to feel it!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11561 - Getting Gold

Make gold an int.
Check input and AC output for thousands of problems on uDebug!

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 11561 - Getting Gold

brianfry713 wrote:Make gold an int.
thanks == BigInteger (Java)
a lot ...what silly mistake ............
we r surrounded by happiness
need eyes to feel it!

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm

### Re: 11561 - Getting Gold

Code: Select all

``````Accepted....
``````
Last edited by shuvokr on Fri Jun 21, 2013 10:37 am, edited 1 time in total.

Code: Select all

``enjoying life ..... ``

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11561 - Getting Gold

Input:

Code: Select all

``````16 25
################
####G..G.#GGTT##
##.##GG#GT#G#G##
#GG#..G.#G.T#.T#
#.GGTG#.G##G.GT#
#TG.#GTT.TG#T..#
#.#T##T.#..#TT.#
#GTGTT..TGGTTG.#
#..##T.TGGG#..T#
#GGGGTG##.TG.#T#
#G#G.###.#..#.##
##..#...T.T.##.#
#TGGT.GTT..PGT##
#G.T#TGTGGG.T.G#
#GT#G#.G.#TG.G.#
#.TT.G.T#.##.#T#
#GTTT#.TG#TGG#G#
#.#G..T#GGG#G#G#
#.TTG##TTT#TG.T#
#G##GG#.G.TGGT##
#GG#.T...TGG####
###..GT.G.#G..G#
#.T#.TG##.#TG###
#.TGT..G.T..GTG#
################
6 16
######
##.T.#
#.GT.#
###.G#
#G#TG#
#GGGG#
#.TG.#
#TT.T#
##..G#
##T.##
#TGT.#
#P.G.#
#..TG#
#.TG.#
#TT.G#
######
9 24
#########
#.#.GTG.#
#.TGGG.G#
#.#.G####
###..T.##
###T#GG##
#TGTGTTG#
#TGTT.GT#
#T..GPT##
#.#TTT..#
#.G.TTG##
##TG#.G.#
#G.GTT.T#
#TG.G#T##
#.GT#GG.#
##G#G####
#T##T####
#.T.GT.G#
#.G#.G.T#
#TGT.G..#
##TT...G#
#TT.G##G#
#.TT.T.##
#########
21 26
#####################
#.G#..T#G#TG##T.T##.#
##TT.G#.#G##.T#TG####
##TG#.#G#.#G#G#.G##.#
#T#T.##T.#.#T#.TG#.G#
#G##TG..G.T###G.T#T.#
##.#GGG.TTTGTT#G#..T#
#.#.TGTT..GG##.G#GTT#
#T###..G.#.#.#G#.GGT#
#..T.T..TT.##GGG#G..#
#.T##TT#.G..T####.TT#
#T#G.GGGG.GG#.TGT#TG#
###.T.TG#...GG#GG#TG#
#.GG.#.G#T.GTT#G#TT##
#.T#.T#T##..##.#TT###
#..T.G#TGG.T.##TTG.##
####TGGG.#TTGGGTGG.T#
#G.GT#.G.GG..#TT.TT.#
#G.GT.GTGGT.#T.#.TT.#
#T#.GTTT#G#.....G#.##
#.G.##TTGG.#.GG#GT.T#
#...###TT.GGT.GGT#T.#
#.T#TG#T###T.TG#.#TT#
#.GTGTGGTT..G#G#.TGG#
#.P##TT.TG#GT..TG.#G#
#####################
19 14
###################
###T.TGGTG.G#GTT#T#
#.##.T..TTGTT#G.GT#
##TT#.T#..#GGG#.#G#
##GG#TTP###G##G.G##
#G.TTTGG.GGG#.#.###
#.G.G#T.#.T##TG#GT#
#.TT.T#.TG...T##TT#
#...#T#..TGG.TT.#.#
##.T#GTTGT##...####
#G.T.##G#TTGG....G#
#T.T#.#GT#.TGT.TGG#
#G##GTGTTGTG.GGG.T#
###################
5 6
#####
#G#T#
#T###
#PT.#
##TG#
#####
16 3
################
#G#.G..G.P.G#G.#
################
20 27
####################
##..TTGGG#GT#T.#.###
##T#TG..G#TT...##GG#
#.TGTTT.#GTT#...#G.#
#TG..TG#GGT#GTTTT#.#
##TT##.G##.G.#T.TGG#
###G#.P##GGGT#..GGT#
##.TG#GGT#TGGTG#GGG#
#.##G##TTTTT##.TGG.#
#GGG.#G..GT.GT....T#
##G#.T.TG..G.#G...T#
#.#TG.GGG..G#T#..TG#
#..G##GTGTG.G#....##
#......TGTG.#T#TTG.#
##TG.#..G##.TT#TGTG#
#..GG..#G#G##.GG..##
#.##TTT.#.G#TGTGGT.#
#..GT.#G.#G#T#T.G.G#
#T##G#GT#TT##TT#T.T#
#..GT..#TGTT.##TG#.#
#TGT#T.T#T..GG#.T.##
#GT.G.GGT#TTGT#G#T##
###G.TG.T####G#...##
#...TGTTT.#GGG##GT.#
#GGT.#.T##GTT.GG#TG#
#.##.G#.GG#TTTTT#G.#
####################
13 12
#############
###TTP#T..T.#
#T.##TT#T..##
#TT..T#T..TT#
#T##..T#TGGG#
####GG..G#GT#
#TG#GTT..#TT#
#GGT#.##.#TT#
#GTTGGT#T#.T#
#T.##.TTG.TG#
#G..###G..TG#
#############
24 28
########################
#.TT####TGT#TTT.TT#T.G.#
#G..T.G#G#TT..GTTT##...#
#T#T#T##TT#TG.GGTG.###T#
##G..#T#TT.G##TGG#T#.#T#
#G##GTG#GTGGG.###..T.T.#
#GT..#T#G##.G.GGTG##G#T#
##G.#.TTGG#TGTGT.GG#.GT#
#GT#G.GTT#.#TTT#.#.T..##
#.GTGG..TG.#.GT.T#TGG.##
##TTGG#..G.GT.GT#TT#.G##
#GG..T..GTT##T#GT#GG##.#
##.TGG..TTGTG.#G#.TGTGT#
#.G#TT#..T##.###T.GTGGG#
#.G.##..#G##.G.T.#.TG#.#
#.GT#G#.T.#T#G.T.TTTGGT#
#.#T#T##.#T..GGT.TGT##T#
##.G.TT.T...GTG#..GT..T#
#.TGGTT#G#G.#GG..###T#.#
##T.TTGGTT.#T..##.G#.###
#.T#TGG.#GT..#T..#G#GT##
#P..G..##TTT#..#.#T..G##
#TTTG.T..#T.TT#G.GTGTG.#
#G#.#.#TGT.T#.TG#G#..GG#
#TGGT#G.#G.G.#GT.G##TT##
##TG..G#.GGGGT#TGGTGGG##
#GTTGGG#T#G##.T##T.#T..#
########################
18 15
##################
#TG.T#G..G..#GT.##
#G#.#GGT#TT#GT#..#
##.GG....#.##GTGG#
#.G.GGG##TG#.###G#
#T#GG#G.G.T..#.G##
#..#G.G#TTGG.##G.#
#PGG.#G...G#..T.T#
#T#.TT..#G.#G#GGT#
#TGT.TG#GGG..##G.#
#G.G#..G.#..G..#G#
#G.GT.#T..T.T..GG#
#.G##.#TTTT#TGGTG#
#.TT#G.T.GGG.GG..#
##################
27 16
###########################
#G#GT.##G#GGTT#.TTTGTTGGTG#
#GGGTT.TGG.P.#T.TTG#.##G..#
#TGGTG##G###G#.G##.GG.TT.G#
#GT#TGT#GT.G.TT#G.####GTTG#
#TG##.#.GGGGT#G#TT#.#G.T#T#
#.GTGTTT#.GTT.#T.##T.T#G.T#
##.G.TT#T#.#GGG.G#T.G###T.#
#T##TT..GG#TTT#GGGGGT.T.GG#
#...TG#.#GG.GG.G#GT.#T.#TG#
#.TT#TTTGG.G.##.#T.#G.TGTG#
###GTGGGTT.##G....#T#TG.T##
#GG.GTG.GGGGGGTT...G##.#GT#
#G#T......GT..T..T..#G.T..#
#G####.#GGT.GT..TG#GTT.#G##
###########################
7 3
#######
#.PGTT#
#######
26 14
##########################
#TG..G.G.#T.GTGTG#T##TG.G#
#GT#.G####TT#GTT##G#.G..##
#GTGTTGT#T.TTT..GGG#GTG#.#
#GG#T.T...GGGG##TTG#..#.G#
##TGGT..#.#...####..#TT.##
#T#TTGGT##T#.G#TGGG...T#T#
#GTGT#.GGTTTTP##GG.#.GGTG#
#GT.GGG##T.##TT#T.G#G#GG##
#G.TG.#GGG.GG.##GTG.##TGT#
#T#T..#T.T..GT.GT#G#T#G#.#
#TT#.##GGGT...T#GGTTTGT.##
##TGGT#G#.#TTGTTG.TG###.##
##########################
7 3
#######
#PT#..#
#######
10 10
##########
#TG.G#TT##
##.#TPG#G#
##T.GT..T#
#G#GGT.G##
#GG#G#.#G#
#TT#.TT..#
###..T#GT#
#GTT#GTGT#
##########
28 17
############################
#T...G##T.TGT..GG#GT#T.G#GT#
#.#.GTTGTGG.###.#.##.#G..#T#
##...G#T.##G#.G.##TGT...T#T#
#T#TG...##P.G.###.TT.GG#TG.#
#GG.##G.GT..T#T.TT.GGT.T##T#
##G#.G#..GT.G#T.T##.T.GG.GT#
##TGT##TGTT.GG.#G.GT.T.TGGG#
#TTGT##.#.TTT###T..GT.GTG.##
#.G..GGGGT..GT###.GT#TGTTTG#
#T#GGG.G.#T..TT#GT...##..GG#
#.T#GT.#TG#GG#.TT#.#G.G.#.T#
#T.GT...T.GTT#TG#T#T...##.T#
##.GTGTGT#GGTTG##TG.T#T.GG.#
#.#T...#.G#GT..TGG#G#TT#G.T#
#T#TTTG.#..TT##G...#G.##.T.#
############################
8 18
########
#GT#T.G#
####TTG#
#.G#..T#
##TT#..#
#TG.#G.#
##GGT#.#
#TG#.T.#
#.G.T.##
###..G.#
#.T.#G.#
#T#GT.##
#TG#.G.#
##.G#PT#
#.G.TG.#
#T.#.#G#
#.#TT###
########
20 27
####################
###TTTTT.#T.T#.GG###
#.T##...T#GTT#.G.GT#
#G#G#..GT.GTT.G#T#T#
#T##.#.GG#GG.TGTT.G#
#T.TG..T#.GG#TTGGG##
#.G.#T.T#.#G##TT.TT#
###.##.GGGGGG#.TTT##
#G#GGGG##TG##TGTG#.#
#G#.G#.TT.##GG..G..#
#TT##TGT#G#..T.TT.G#
#GGT.#.G##..T#G.G#G#
#G..TT#G.TTGGTGT#G.#
##G#G.T#TTT#.T#.G.G#
##...T.G#GTTGGP.G#.#
#..TGG##GGT.GG..G.##
#T##.#.G#G.##.T#G###
#.G#.TT.#T##GT.#.#T#
#....##TT..#T#T#GG.#
##.T.#...#T#T#TG#G##
#G#G.T#T...G.###GTG#
#.G.#T#.G..#GT##TT.#
#.#.#T.TGTGG#G.#GT.#
##G.T.TTT..#T.#.#GT#
#T#T##TG#G###TG#T###
##..#.T.#.#GG.T#G.G#
####################
20 10
####################
#TTG#T#..G#..G#T.GG#
#TGGTT#TG#..TTG#T#.#
#.#.GG#.GGG.GTGGTTT#
#G.T##G..GTG#T.GG.G#
##.G#..#GG##T.#GGG##
#GGTGTT##T.#G.G.G#.#
#.G..#TTT.TPTGGTGTT#
#T.GGG.#G#.G#T.###T#
####################
``````
AC output:

Code: Select all

``````1
0
0
1
0
0
3
4
0
0
0
4
1
0
0
0
4
0
13
0
``````
Check input and AC output for thousands of problems on uDebug!

New poster
Posts: 6
Joined: Fri Jun 21, 2013 3:31 am

### Re: 11561 - Getting Gold

I have tried a lot of test cases , but getting WA every time .
Will anyone help me, finding the wrong in my code . Thanks

Code: Select all

``````#include <stdio.h>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <iostream>

using namespace std;

#define sf scanf
#define pf printf
#define maxm 100000
#define mem(a,b) memset(a,b,sizeof(a))
#define eps 1e-9

int wi,hi;
char V[55][55],gold;

int dir[4][2]={ {0,1}, {0,-1}, {1,0}, {-1,0} };

bool isvalid(int r,int c){
if(c<0 || c>=wi || r<0 || r>=hi) return false;
return true;
}

void search_gold(int si,int sj){

int i,j,k;

if(V[si][sj]=='G'){
gold++;
V[si][sj]='.';

}

if(V[si][sj+1]=='T' || V[si][sj-1]=='T' || V[si+1][sj]=='T' || V[si-1][sj]=='T'){ V[si][sj]='#'; return; }

V[si][sj]='#';

int ti,tj;
for(i=0;i<4;i++){
ti=si+dir[i][0];
tj=sj+dir[i][1];
if(isvalid(ti,tj)==true && V[ti][tj] != '#' && V[ti][tj]!='T' ) search_gold(ti,tj);
}

}

int main(){

int cases=0,i,j,k,t,N;
while(sf("%d %d",&wi,&hi)!=EOF){

gold=0;
for(i=0;i<hi;i++) sf("%s",&V[i]);

int tag=0,si,sj;
for(i=0;i<hi;i++){
for(j=0;j<wi;j++){
if(V[i][j]=='P'){
si=i;
sj=j;
tag=1;
break;
}
}
if(tag==1) break;
}

search_gold(si,sj);
pf("%d\n",gold);

}
return 0;
}

``````

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm

### Re: 11561 - Getting Gold

Code: Select all

``````Thanks  brianfry713 .
``````

Code: Select all

``enjoying life ..... ``

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11561 - Getting Gold

Loading... wrote:I have tried a lot of test cases , but getting WA every time .
Will anyone help me, finding the wrong in my code . Thanks
make gold an int
Check input and AC output for thousands of problems on uDebug!

Alim14
New poster
Posts: 8
Joined: Sun Jan 05, 2014 3:40 pm

### Re: 11561 - Getting Gold

When a player stands next to one or more trap, he sense a draft but as he don't know from where the draft comes,so he cant move from his position. This is the main challenge.
When I believe it is possible, I always find a way

Alim14
New poster
Posts: 8
Joined: Sun Jan 05, 2014 3:40 pm

### Re: 11561 - Getting Gold

Input:

Code: Select all

``````5 5
#####
GGGGG
TGTGT
GGGGG
GTGTP``````
Output:

Code: Select all

``0``
When I believe it is possible, I always find a way

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

### Cannot understand the question

It is written that every trap sends a draft to its adjacent(top, bottom,left, right) location. Does this mean that if there is a gold at the draft postion , it should not be counted?

If not, then please explain with respect to examples given in the question. As far as I can understand, in these examples, they have considered the gold kept in the draft position.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11561 - Getting Gold

Yes you can collect gold in a draft position.
In the first sample input there is only one gold you can collect without falling into a trap and that is a draft position.
In the second sample input you can collect all of the gold in the 5th column, but can't get to the gold in the 7th column without risking falling into a trap.
Check input and AC output for thousands of problems on uDebug!