10653 - Bombs! NO they are Mines!!

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

Moderator: Board moderators

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

WA.....10653 - Bombs! NO they are Mines!!

Post by LazyTym » Wed Aug 27, 2014 10:57 pm

Code: Select all

#include<iostream>
#include<queue>
#include<ctime>

using namespace std;
static int m[1010][1010];
int sx,sy,dx,dy,num_row,num_column;
int dif_x[] = {1,-1,0,0};
int dif_y[] = {0,0,1,-1};

typedef struct
{
    int x,y,steps;
} point;

int search_dest(int x,int y)
{
     point start;
     start.x=x;
     start.y=y;
     start.steps=0;

     queue<point>q;
     q.push(start);
     m[x][y]=1;


     while(!q.empty())
     {

         point top=q.front();
         q.pop();
         x=top.x;
         y=top.y;

         if(x==dx && y==dy) return (top.steps);


         for(int i=0;i<3;i++)
         {
             x=x+dif_x[i];
             y=y+dif_y[i];

             if(x>=0 && y>=0 && x<=num_column && y<=num_row && m[x][y]==0)
             {
                 point next;
                 next.steps=top.steps+1;;
                 next.x=x;
                 next.y=y;
                 m[x][y]=1;

                 q.push(next);

             }
         }
     }
     return 0;

}


int main()
{
    //int start_s=clock();
	// the code you wish to time goes here

    int y,x,num_bombs,row;
    while(1)
    {
        cin>>num_row>>num_column;
        if(num_row==0 && num_column==0) break;
        cin>>row;
    for(int i=0;i<row;i++)
    {
        cin>>x;
        cin>>num_bombs;
        for(int j=0;j<num_bombs;j++)
        {
            cin>>y;
            m[x][y]=1;
        }
    }

    cin>>sx>>sy;
    cin>>dx>>dy;

    cout<<search_dest(sx,sy)<<endl;
    //int stop_s=clock();
    //cout << "time: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000000 << endl;
    }


    return 0;
}


lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: WA.....10653 - Bombs! NO they are Mines!!

Post by lighted » Thu Aug 28, 2014 12:13 am

Post in existing threads. Don't open new thread.

Change line to

Code: Select all

for(int i=0;i<4;i++)
Change order of x and y

Code: Select all

if(x>=0 && y>=0 && y<=num_column && x<=num_row && m[x][y]==0)
You are loosing values of x and y after i = 0. Add new variables this way

Code: Select all

int X=x+dif_x[i];
int Y=y+dif_y[i];

if(X>=0 && Y>=0 && Y<=num_column && X<=num_row && m[X][Y]==0)
{
  point next;
  next.steps=top.steps+1;;
  next.x=X;
  next.y=Y;
  m[X][Y]=1;
You must clear array m for each case.

Code: Select all

if(num_row==0 && num_column==0) break;

memset(m, 0, sizeof(m));

cin>>row;
Don't forget to remove your code after getting accepted. 8)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Nahian.Sunny
New poster
Posts: 6
Joined: Tue Oct 21, 2014 12:51 pm

Re: 10653 - Bombs! NO they are Mines!!

Post by Nahian.Sunny » Tue Feb 03, 2015 7:31 am

Why WA? Plz help

Code: Select all

Removed after AC
Last edited by Nahian.Sunny on Thu Feb 05, 2015 11:42 am, edited 1 time in total.

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

Re: 10653 - Bombs! NO they are Mines!!

Post by brianfry713 » Thu Feb 05, 2015 1:33 am

The test case ends with the starting location (row, column) followed by your destination (row, column).
You're not reading that info, it looks like your code assumes that the starting location is always (0, 0) and destination is always (R-1, C-1)
Check input and AC output for thousands of problems on uDebug!

Nahian.Sunny
New poster
Posts: 6
Joined: Tue Oct 21, 2014 12:51 pm

Re: 10653 - Bombs! NO they are Mines!!

Post by Nahian.Sunny » Thu Feb 05, 2015 11:41 am

oh! how silly of me! got acc now... thnx brianfry :D

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 10653 - Bombs! NO they are Mines!!

Post by Shahidul.CSE » Sat May 16, 2015 4:24 am

My code can't run for the given sample input. May be there is problem in recursion. But I can't figure it out. Here is my code:
[also can see at http://pastebin.com/SvTbMRYZ ]

Code: Select all

#include <string.h>
#include <stdio.h>
#define MIN(a, b) (a<b ? a:b)

int grid[1002][1002], dp[1002][1002], Row, Colum, startRow, startColum, destinationRow, destinationColum;
int lowestPath(int r, int c)
{
    if(r==destinationRow && c==destinationColum)
        return 0;
    int up, left, down, right;
    up = left = down = right = 10000000; //by default, set a very big value so that it can't me minimum

    if(r>0)
    {
        if(dp[r-1][c] > 0)
            up = dp[r-1][c];
        else if(grid[r-1][c] != 0) // check if there is a bomb or not
            up = 1 + lowestPath(r-1, c);
    }

    if(r < Row-1)
    {
        if(dp[r+1][c]>0)
            down = dp[r+1][c];
        else if(grid[r+1][c] != 0) // check if there is a bomb or not
            down = 1 + lowestPath(r+1, c);
    }

    if(c>0)
    {
        if(dp[r][c-1]>0)
            left  = dp[r][c-1];
        else if(grid[r][c-1]!=0)   // check if there is a bomb or not
            left = 1 + lowestPath(r, c-1);
    }

    if(c<Colum-1)
    {
        if(dp[r][c+1]>0)
            right = dp[r][c+1];
        else if(grid[r][c+1]!=0)   // check if there is a bomb or not
            right = 1 + lowestPath(r, c+1);
    }
    dp[r][c] = MIN(MIN(up, down), MIN(left, right));
    return dp[r][c];
}
int main()
{
    //freopen("10653.txt", "r", stdin);
    int row, col, i, j, bomb, amount, ans;
    while(scanf("%d %d", &Row, &Colum)!=EOF)
    {
        if(Row==0 && Colum==0)
            break;
        for(i=0; i<Row; i++)
            for(j=0; j<Colum; j++)
                grid[i][j] = 1;   //possible to go away by this point of grid, so set 1
        scanf("%d", &bomb); //how many row contain one or more bomb ?
        for(i=0;i<bomb;i++)
        {
            scanf("%d %d", &row, &amount); //in which row and how many bomb in that row?
            for(j=0;j<amount;j++)
            {
                scanf("%d", &col);  // in which column of that row contain a bomb
                grid[row][col]=0;  //there is bomb! so not possible to go away by this point of grid, and so set 0
            }
        }
        memset(dp, 0, sizeof(dp)); //no path is calculated
        scanf("%d %d %d %d", &startRow, &startColum, &destinationRow, &destinationColum); //from which position? and where to go?
        ans=lowestPath(startRow, startColum);
        printf("%d\n", ans);
    }
    return 0;
}
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

reshad555
New poster
Posts: 1
Joined: Wed Apr 06, 2016 10:43 am

Re: 10653 - Bombs! NO they are Mines!!

Post by reshad555 » Mon Sep 05, 2016 1:11 pm

this is my dp solution. I've tested it with a few cases but getting wa. can anyone tell me what is wrong with my code,please.

Code: Select all

#include<bits/stdc++.h>
using namespace std;
#define asgnarr(a,n) for(int i=0;i<n;i++)cin>>a[i]
#define fast ios_base::sync_with_stdio(false)
#define loop(a,b) for(int i=a;i<b;i++)
#define mem(a,x) memset(a,x,sizeof(a))
#define pii pair<int,int>
#define psi pair<string,int>
#define pss pair<string,string>
#define inf 2e9

typedef long long lli;
typedef long li;
typedef unsigned long long ulli;
typedef unsigned long int uli;
typedef unsigned int ui;
typedef long double ld;

inline int iseven(int x){return x&1?0:1;}
inline bool is_double(double x){
    double y=x-(int)x;
    return (y==x?true:false);
}

int sx,sy,dx,dy;

int a[1007][1007];
int visited[1007][1007];
int dp[1007][1007],r,c;

int shortest(int i,int j)
{
    if(i<0 || j<0 || i>=r || j>=c)
        return inf;
    if(i==dx && j==dy)
        return 0;
    if(dp[i][j]!=-1)
        return dp[i][j];
    if(visited[i][j]==0)
        visited[i][j]=1;
    else
        return inf;
    if(a[i][j]==1)
        return inf;
    int m1,m2,m3,m4;
    m1=shortest(i,j+1)+1;
    m2=shortest(i-1,j)+1;
    m3=shortest(i,j-1)+1;
    m4=shortest(i+1,j)+1;

    return dp[i][j]=min(m1,min(m2,min(m3,m4)));
}

int main()
{
    fast;
    while(cin>>r>>c,r&&c)
    {
        mem(a,0);
        mem(visited,0);
        int n;
        cin>>n;
        while(n--)
        {
            int row,x,col;
            cin>>row>>x;
            while(x--)
            {
                cin>>col;
                a[row][col]=1;
            }
        }
        cin>>sx>>sy>>dx>>dy;
        mem(dp,-1);
        cout<<shortest(sx,sy)<<endl;
    }
}



Post Reply

Return to “Volume 106 (10600-10699)”