11561 - Getting Gold

[Obaida]

Thank you brother i found my mistake.

[Shafaet_du]

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

[outsbook]

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.

[mahade hasan]

cut>>>>>>>>>

[brianfry713]

Make gold an int.

[mahade hasan]

Make gold an int.

thanks == BigInteger (Java)
a lot ...what silly mistake ............

[shuvokr]

Code: Select all

Accepted....

[brianfry713]

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

[Loading...]

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]

Code: Select all

Thanks  brianfry713 .

[brianfry713]

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

[Alim14]

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.

[Alim14]

Input:

Code: Select all

5 5
#####
GGGGG
TGTGT
GGGGG
GTGTP

Output:

Code: Select all

0

[richatibrewal]

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]

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.