10653 - Bombs! NO they are Mines!!

[LazyTym]

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]

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.

[Nahian.Sunny]

Why WA? Plz help

Code: Select all

Removed after AC

[brianfry713]

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)

[Nahian.Sunny]

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

[Shahidul.CSE]

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;
}

[reshad555]

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;
    }
}