OJ Board

Posted: **Fri Aug 14, 2009 10:40 pm**

Hi calicratis19,

I think, that the reason of RTE may be here:

array[1103]

and then

Code: Select all

else if(cha=='F')
            {
               array[y]=i;
               array[y+1]=j;
               y+=2;
               Adjacent [ i ][ j ] = 1;
            }

Think about case, when the maze has 1000 rows, 1000 columns and here is one "J" and 999999 "F". Array array should have length 1999998 (or little bit more - for insure). Think about length of other arrays in your program too. If the length is too short, it causes RTE.

Hope it helps and you will get AC now

Posted: **Sat Aug 15, 2009 11:02 am**

sorry that i havent edited my code . i have noticed the mistake that u have pointed here. i already changed my array size.but its wa now. can u pls tell me why wa now. thanks for your reply.

Posted: **Sat Aug 15, 2009 8:31 pm**

Try to think how to solve this problem with one BFS!!!

Posted: **Sat Aug 15, 2009 11:53 pm**

As Igor9669 wrote, one BFS is enough. In each step of BFS, at first "extend" the fire () and at second "extend" the move of Joe. I don't understand your implementation clearly, I used three 2-dimensional array, one for reading input, one for movement of Joe and one for extension of fire.

Posted: **Sun Aug 16, 2009 12:00 am**

I try run your program and I think, that I found some wrong outputs.

For example, for input:

Code: Select all

5
1 1
J
1 2
J.
2 1
.
J
2 2
..
.J
2 2
..
FJ

your program returns

Code: Select all

IMPOSSIBLE
2
2
2
2

but correct output is

Code: Select all

So, try to fix it, or think about only one BFS, or another implementation. Hope you will get AC now

Posted: **Mon Aug 24, 2009 7:42 pm**

i got ac. thank you jurajz and Igor9669. i used two bfs though

Posted: **Thu Dec 31, 2009 6:06 pm**

hi everyone,i am getting run time error a lot in this prob.
could anyone check my code to tell the cause of wa.
//code here
#include<stdio.h>
#include<stdlib.h>
#define inf 100000

int fire[1005][1005],min;
char input[1005][1005];
int row,col,que[1000005][3],r[]={0,0,-1,1},c[]={-1,1,0,0};

void BFS(int rr,int cc,int var);

int main()
{
int test,i,j,m,n;

scanf("%d",&test);

while(test--)
{
scanf("%d %d",&row,&col);

for(i=0;i<row;i++)
scanf("%s",input);
for(i=0;i<row;i++)
for(j=0;j<row;j++)
fire[j]=inf;

for(i=0;i<row;i++)
for(j=0;j<row;j++)
{
if(input[j]=='F')
{
BFS(i,j,1);
}
if(input[j]=='J')
{
m=i;n=j;
}
}
/*for(i=0;i<row;i++){
for(j=0;j<col;j++)
printf("%d ",fire[j]);
printf("\n");
}*/

min=inf;
BFS(m,n,0);
if(min==inf)
printf("IMPOSSIBLE\n");
else printf("%d\n",min);
}
return 0;
}

void BFS(int rr,int cc,int var)
{
int i,m,n,front,rear;

if(var) fire[rr][cc]=0;
else if(rr==0||rr==row-1||cc==0||cc==col-1)
{ min=1;return;}

front=rear=0;
que[rear][0]=rr;
que[rear][1]=cc;
que[rear][2]=0;
rear++;

while(front!=rear)
{
for(i=0;i<4;i++)
{
m=que[front][0]+r;
n=que[front][1]+c;

if((m>=0&&m<row)&&(n>=0&&n<col))
if( input[m][n]!='#' && que[front][2]+1<fire[m][n])
{
que[rear][0]=m;
que[rear][1]=n;
que[rear++][2]=que[front][2]+1;
if(var)
fire[m][n]=que[front][2]+1;
else if(m==0||m==row-1||n==0||n==col-1)
{
if(que[front][2]+2<min)
min=que[front][2]+2;
}

}
}
front++;
}
}

Posted: **Sun Mar 14, 2010 2:18 pm**

Code: Select all

#include <stdio.h>
#include <string.h>
#define inf 99999999
#define sz 1100
#define SZ 1100110
long r[]={0,0,-1,1},c[]={-1,1,0,0},dist_joe[sz][sz],dist_fire[sz][sz];
long cur_x,cur_y,que_x[SZ],que_y[SZ],head,tail;
long m,n,test,row,col,i,j,no_fire,joe_x,joe_y,cost;
char array[sz][sz];

void bfs_fire(int x,int y)
{
    int i;
    head = tail = 0;  que_x[tail]=x; que_y[tail++]=y; dist_fire[x][y]=1;
    while(head != tail)
    {
        cur_x=que_x[head]; cur_y=que_y[head++];
        for(i=0;i<4;++i)
        {
            m=cur_x+r[i]; n=cur_y+c[i];
            if(m<0 || n<0 || m>=row || n>=col)
                continue;
            if( array[m][n]=='.' && dist_fire[cur_x][cur_y]+1 < dist_fire[m][n])
            {
                dist_fire[m][n]=dist_fire[cur_x][cur_y]+1;
                que_x[tail]=m; que_y[tail++]=n;
            }
        }
    }
}

void bfs_joe(int x,int y)
{
    int i;
    head = tail = 0;  que_x[tail]=x; que_y[tail++]=y; dist_joe[x][y]=1;
    while(head != tail)
    {
        cur_x=que_x[head]; cur_y=que_y[head++];
        for(i=0;i<4;++i)
        {
            m=cur_x+r[i]; n=cur_y+c[i];
            if(m<0 || n<0 || m>=row || n>=col)
                continue;
            if( array[m][n]=='.' &&  dist_joe[cur_x][cur_y]+1 < dist_fire[m][n])
            {
                array[m][n]='#';
                dist_joe[m][n]=dist_joe[cur_x][cur_y]+1;
                que_x[tail]=m; que_y[tail++]=n;
            }
        }
    }
}

int main()
{
    scanf("%ld",&test);
    while(test--)
    {
        scanf("%ld %ld",&row,&col);
        for(i=0;i<row;++i)
            scanf("%s",array[i]);
        for(i=0;i<=row;i++)
            for(j=0;j<=col;j++)
                dist_fire[i][j]=dist_joe[i][j]=inf;
        for(i=0;i<row;++i)
            for(j=0;j<col;++j)
            {
                if(array[i][j]=='J')
                    joe_x=i , joe_y=j;
                if(array[i][j]=='F')
                    bfs_fire(i,j);
            }
        bfs_joe(joe_x,joe_y);
        cost=inf;
        for(i=0;i<row;++i)
            for(j=0;j<col;++j)
            {
                if((i==0 || j==0 || i==row-1 || j==col-1) && dist_joe[i][j] < cost )
                    cost=dist_joe[i][j];
            }
        if(cost==inf)
            printf("IMPOSSIBLE\n");
        else
            printf("%ld\n",cost);
    }
    return 0;
}

Posted: **Mon Mar 15, 2010 11:32 am**

Ur code and logic is ok .
U can speedup it by returning ur answer from j_bfs but not cheacking in main.
Ur code got accepted when I use int against long.
Becos u know may be assigning long array or initialising takes more time here.

Good regards Friend.

Posted: **Mon Mar 15, 2010 12:28 pm**

thank u frnd i became foolish when i got accepted after changing data type int instead of long

Posted: **Sat Jul 24, 2010 9:27 pm**

getting WA! please help! thanks in advance

Code: Select all



#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAX 1010
using namespace std;
int r,c;
char grid[MAX][MAX];
bool flag=false;
struct Node{
   int x;
   int y;
};
int dj[MAX][MAX];
int arr[]={-1,0,1,0,0,-1,0,1};
void bfs(Node s,Node y)
{
   queue<Node> f;
   queue <Node> j;
   dj[s.x][s.y]=1;
   j.push(s);
   f.push(y);
   int u,v;
   while(!j.empty())
   {
      Node tmp=j.front();j.pop();
      if(grid[tmp.x][tmp.y]!='F') //for J
      {
         for(int i=0;i<8;i+=2)
         {
            int row=tmp.x+arr[i];
            int col=tmp.y+arr[i+1];
            if(row>=0 && row<r && col>=0 && col<c )
            {
               if(grid[row][col]=='.')
               {
                  Node t;   t.x=row; t.y=col;
                  j.push(t);
                  dj[row][col]=dj[tmp.x][tmp.y]+1;
                  grid[row][col]='J';
               }
            }
            else //if in last or first row or column
            {   
               //cout<<tmp.x<<" "<<tmp.y<<" "<<dj[tmp.x][tmp.y]<<endl;
               cout<<dj[tmp.x][tmp.y]<<endl;
               flag=true; return;
               u=tmp.x;
               v=tmp.y;
            }
         }
      }
      if(!j.empty()) //for fire
      {
         tmp=f.front();f.pop();   
         for(int i=0;i<8;i+=2)
         {
            int row=tmp.x+arr[i];
            int col=tmp.y+arr[i+1];
            if(row>=0 && row<r && col>=0 && col<c )
            {
               if(grid[row][col]=='.'|| grid[row][col]=='J')
               {
                  Node t;   t.x=row;
                  t.y=col; f.push(t);
                  grid[row][col]='F';
               }
            }
         }
      }
   }
}


int main()
{
   int t;
   scanf("%d",&t);
   for(int m=0;m<t;m++)
   {
      scanf("%d%d",&r,&c);
      for(int i=0;i<r;i++)
         scanf("%s",grid[i]);         
      Node s,y;
      s.x=-1;
      for(int i=0;i<r;i++)
         for(int j=0;j<c;j++)
         {
            if(grid[i][j]=='J')
               s.x=i,s.y=j;
            else if(grid[i][j]=='F')
               y.x=i,y.y=j;
         }
      flag=false;
      if(s.x!=-1)
      bfs(s,y);   
      if(!flag)
         printf("IMPOSSIBLE\n");
   }
   return 0;
}

Posted: **Thu Nov 04, 2010 9:39 pm**

I solved the problem running two Breadth First Search at a time. First check where fire can go from initial positions then check where Joe can go. assign current position to initial position and repeat the steps until joe reach safety point,thats is on the edge of the matrix. If joe has no where to go then print IMPOSSIBLE. check this I/O:

Code: Select all

4
10 10
##########
#.....JFF#
#........#
#........#
#........#
#........#
#........#
#........#
#........#
..########
3 1
#
J
F
1 2
.J
5 5
#####
#..F#
#.J.#
....F
#####

output:

Code: Select all

you should get ac now

.
happy programing

Posted: **Sun Nov 06, 2011 3:59 am**

Hey all i am getting RTE in FIRE 11624.. .. ?? would be helped a lot if any one can take me out of this bad situation .. thanks in advanced ::-::-::-

Code: Select all

#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;
int mani(int a,int b){
	return a<b?a:b;
}

struct node{
	int u,v;
}temp,joe;
vector<node>fires;

int n,m;
string grid[1010];

int movex[]={0,0,1,-1};
int movey[]={1,-1,0,0};
bool visit[1010][1010];
int len[1010][1010],len1[1010][1010];
queue<node>q;

void BFS_FIRE(node start,bool hat){
//	cout<<"okp"<<endl;
	for(int j=0;j<n;j++){
		for(int k=0;k<m;k++)visit[j][k]=false;
	}
	visit[start.u][start.v]=true;
	if(hat==true)len[start.u][start.v]=0;
	else len1[start.u][start.v]=0;
	q.push(start);
	while(!q.empty()){
		temp=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			node lol;
			lol.u=temp.u+movex[i];
			lol.v=temp.v+movey[i];
			if(hat==true){
				if(grid[lol.u][lol.v]!='#'&&visit[lol.u][lol.v]==false&&len[lol.u][lol.v]>len[temp.u][temp.v]+1&&(lol.u>=0&&lol.u<n)&&(lol.v>=0&&lol.v<m)){
					visit[lol.u][lol.v]=true;
					len[lol.u][lol.v]=len[temp.u][temp.v]+1;
					q.push(lol);
				}
			}
			else {
				if(grid[lol.u][lol.v]!='#'&&visit[lol.u][lol.v]==false&&(lol.u>=0&&lol.u<n)&&(lol.v>=0&&lol.v<m)){
					visit[lol.u][lol.v]=true;
					len1[lol.u][lol.v]=len1[temp.u][temp.v]+1;
					q.push(lol);
				}
			}
		}
	}
}


int main()
{
	freopen("sam.txt","r",stdin);
	int i,t,j,k;
	cin>>t;
	for(i=0;i<t;i++){
		cin>>n>>m;
		for(j=0;j<n;j++)cin>>grid[j];
		for(j=0;j<n;j++){
			for(k=0;k<m;k++){
				if(grid[j][k]=='J'){
					joe.u=j;
					joe.v=k;
				}
				if(grid[j][k]=='F'){
					temp.u=j;
					temp.v=k;
					fires.push_back(temp);
				}
			}
		}
		for(j=0;j<n;j++){
			for(k=0;k<m;k++)len[j][k]=len1[j][k]=1000;
		}
		for(j=0;j<fires.size();j++)BFS_FIRE(fires[j],true);
		BFS_FIRE(joe,false);
		int mini=1000;
		for(j=0;j<m;j++){
			if(len1[0][j]<len[0][j])mini=mani(mini,len1[0][j]);
		}
		for(j=0;j<m;j++){
			if(len1[n-1][j]<len[n-1][j])mini=mani(mini,len1[n-1][j]);
		}
		for(j=0;j<n;j++){
			if(len1[j][0]<len[j][0])mini=mani(mini,len1[j][0]);
		}
		for(j=0;j<n;j++){
			if(len1[j][m-1]<len[j][m-1])mini=mani(mini,len1[j][m-1]);
		}
		if(mini==1000)cout<<"IMPOSSIBLE"<<endl;
		else cout<<mini+1<<endl;
		fires.clear();
	}
	return 0;
}

Posted: **Tue Jul 24, 2012 6:02 am**

i used one BFS more specifically Multi SSSP whit floodfill for memory saving in java, is a great problem to solve

. And also a simple self implemented queue that was help from a friend.

Code: Select all

removed after AC.

OJ Board

11624 - Fire!

11624 - Fire!

Re: 11624 - Fire!

Re: 11624 - Fire!

Re: 11624 - Fire!

Re: 11624 - Fire!

Re: 11624 - Fire!

Re: 11624 - Fire!

Re: 11624 - Fire!

why i got RTE in fire 11624

Re: 11624 - Fire!

Re: 11624 - Fire!

Re: 11624 - Fire!

Re: 11624 - Fire!

Re: 11624 - Fire!

Re: 11624 - Fire!