11561 - Getting Gold

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11561 - Getting Gold

Post by Obaida » Mon Jan 12, 2009 7:20 am

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
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11561 - Getting Gold

Post by Shafaet_du » Thu Jun 23, 2011 3:51 pm

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

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

11561 - Getting Gold

Post by outsbook » Thu Nov 24, 2011 11:30 pm

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

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 11561 - Getting Gold

Post by mahade hasan » Thu Sep 13, 2012 6:07 am

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

Post by brianfry713 » Thu Sep 13, 2012 9:47 pm

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

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 11561 - Getting Gold

Post by mahade hasan » Sat Sep 15, 2012 4:25 pm

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
Location: Bangladesh

Re: 11561 - Getting Gold

Post by shuvokr » Thu Jun 20, 2013 2:28 pm

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

Post by brianfry713 » Fri Jun 21, 2013 12:05 am

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!

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

Re: 11561 - Getting Gold

Post by Loading... » Fri Jun 21, 2013 3:43 am

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
Location: Bangladesh

Re: 11561 - Getting Gold

Post by shuvokr » Fri Jun 21, 2013 10:38 am

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

Post by brianfry713 » Sat Jun 22, 2013 7:05 am

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
Location: BUBT,Dhaka, Bangladesh

Re: 11561 - Getting Gold

Post by Alim14 » Sat Feb 01, 2014 8:07 pm

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
Location: BUBT,Dhaka, Bangladesh

Re: 11561 - Getting Gold

Post by Alim14 » Sat Feb 01, 2014 8:10 pm

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

Post by richatibrewal » Sun Feb 08, 2015 12:53 pm

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

Post by brianfry713 » Tue Feb 10, 2015 1:49 am

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!

Post Reply

Return to “Volume 115 (11500-11599)”