11624 - Fire!

All about problems in Volume 116. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

11624 - Fire!

Post by calicratis19 » Thu Jul 30, 2009 6:04 pm

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!

Post by jurajz » Fri Aug 14, 2009 10:40 pm

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
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 11624 - Fire!

Post by calicratis19 » 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.
Heal The World

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

Re: 11624 - Fire!

Post by Igor9669 » Sat Aug 15, 2009 8:31 pm

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!

Post by jurajz » 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.

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

Re: 11624 - Fire!

Post by jurajz » 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

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
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 11624 - Fire!

Post by calicratis19 » Mon Aug 24, 2009 7:42 pm

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

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

Re: 11624 - Fire!

Post by bm_anas » 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++;
}
}

nayimsust
New poster
Posts: 9
Joined: Wed Aug 27, 2008 6:50 pm

why i got RTE in fire 11624

Post by nayimsust » 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;
}

matrix
New poster
Posts: 3
Joined: Tue Aug 04, 2009 1:30 pm

Re: 11624 - Fire!

Post by matrix » 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. :lol:

nayimsust
New poster
Posts: 9
Joined: Wed Aug 27, 2008 6:50 pm

Re: 11624 - Fire!

Post by nayimsust » 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

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

Re: 11624 - Fire!

Post by shantanu18 » 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;
}


Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11624 - Fire!

Post by Shafaet_du » 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

14
1
1
4
you should get ac now :wink: .
happy programing

SIMPLE_SIMON
New poster
Posts: 1
Joined: Sun Nov 06, 2011 3:48 am

Re: 11624 - Fire!

Post by SIMPLE_SIMON » 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;
}

civilian
New poster
Posts: 1
Joined: Tue Jul 24, 2012 5:54 am

Re: 11624 - Fire!

Post by civilian » 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.

Post Reply

Return to “Volume 116 (11600-11699)”