11624 - Fire!

[calicratis19]

AC

[jurajz]

Hi calicratis19,

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

Code: Select all

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

[calicratis19]

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.

[Igor9669]

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

[jurajz]

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.

[jurajz]

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

1
1
1
1
1

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

[calicratis19]

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

[bm_anas]

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

[nayimsust]

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

[matrix]

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.

[nayimsust]

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

[shantanu18]

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

[Shafaet_du]

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

14
1
1
4

you should get ac now .
happy programing

[SIMPLE_SIMON]

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

[civilian]

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.