## 11624 - Fire!

Moderator: Board moderators

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Contact:

### 11624 - Fire!

AC
Last edited by calicratis19 on Wed Nov 18, 2009 7:47 pm, edited 1 time in total.
Heal The World

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

### Re: 11624 - Fire!

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
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Contact:

### Re: 11624 - Fire!

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.
Heal The World

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11624 - Fire!

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

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

### Re: 11624 - Fire!

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
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

### Re: 11624 - Fire!

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
``````

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
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Contact:

### Re: 11624 - Fire!

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

bm_anas
New poster
Posts: 10
Joined: Fri May 15, 2009 9:13 pm

### Re: 11624 - Fire!

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
New poster
Posts: 9
Joined: Wed Aug 27, 2008 6:50 pm

### why i got RTE in fire 11624

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 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;
{
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;
{
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
New poster
Posts: 3
Joined: Tue Aug 04, 2009 1:30 pm

### Re: 11624 - Fire!

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
New poster
Posts: 9
Joined: Wed Aug 27, 2008 6:50 pm

### Re: 11624 - Fire!

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

shantanu18
New poster
Posts: 22
Joined: Tue Jul 20, 2010 9:55 pm

### Re: 11624 - Fire!

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
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 11624 - Fire!

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
New poster
Posts: 1
Joined: Sun Nov 06, 2011 3:48 am

### Re: 11624 - Fire!

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
New poster
Posts: 1
Joined: Tue Jul 24, 2012 5:54 am

### Re: 11624 - Fire!

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.``