OJ Board

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

Code: Select all

for(int i=0;i<4;i++)

Code: Select all

if(x>=0 && y>=0 && y<=num_column && x<=num_row && m[x][y]==0)

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;

Code: Select all

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

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

cin>>row;

Code: Select all

Removed after AC

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

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