## 11624 - Fire!

Moderator: Board moderators

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 11624 - Fire!

TLE continue ...
Last edited by mahade hasan on Tue Nov 12, 2013 5:46 pm, edited 1 time in total.
we r surrounded by happiness
need eyes to feel it!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11624 - Fire!

Try first determining the distance from the nearest fire to each square, then the distance from Joe to each square. Then check the edges for the minimum distance from Joe and there before the fire.
Check input and AC output for thousands of problems on uDebug!

Sabiha_Fancy
New poster
Posts: 24
Joined: Mon Jul 16, 2012 3:43 pm

### Re: 11624 - Fire!

I am getting wa. Help me

Here is my code
#include<stdio.h>
#include<stdlib.h>
#define size 1010

char maze[size][size];
int r1[4]={-1,1,0,0};
int c1[4]={0,0,1,-1};
int impossible,min,r,c;

void dfs(char maze[size][size], int row, int col,int count);

int main()
{
int t,row,col,i,j,f;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&r,&c);
fflush(stdin);
for(i=0; i<r; ++i)
{
for(j=0; j<c; ++j)
{
scanf("%c",&maze[j]);
}
fflush(stdin);
}
f=0;
for(i=0; i<r; ++i)
{
for(j=0; j<c; ++j)
{
if(maze[j]=='J')
{
row=i;
col=j;
f=1;
break;
}
}
if(f==1)
break;
}
impossible = -1;
min=2147483600;
dfs(maze,row,col,0);
if(impossible==1)
printf("IMPOSSIBLE\n");
else if(impossible==0)
printf("%d\n",min);
}
return 0;
}

void dfs(char maze[size][size], int row, int col,int count)
{
int i,j,up,down,left,right,help,flag;
if(row==0 || row==(r-1) || col==0 || col==(c-1))
{
count++;
if(min>count)
min=count;
impossible = 0;
return;
}
for(i=0; i<r; ++i)
{
for(j=0; j<c; ++j)
{
if(maze[j]=='F')
{
up=i-1;
down=i+1;
left=j-1;
right=j+1;
if(up>=0 && up<r && j>=0 && j<c && maze[up][j]!='#' && maze[up][j]!='F')
{
maze[up][j]='N';
}
if(down>=0 && down<r && j>=0 && j<c && maze[down][j]!='#' && maze[down][j]!='F')
{
maze[down][j]='N';
}
if(i>=0 && i<r && left>=0 && left<c && maze[left]!='#' && maze[left]!='F')
{
maze[left]='N';
}
if(i>=0 && i<r && right>=0 && right<c && maze[right]!='#' && maze[right]!='F')
{
maze[right]='N';
}
}
}
}
for(i=0; i<r; ++i)
{
for(j=0; j<c; ++j)
{
if(maze[j]=='N')
maze[i][j]='F';
}
}
flag=0;
for(i=0; i<4; ++i)
{
up=row+r1[i];
down=col+c1[i];
help=count;
if(up>=0 && up<r && down>=0 && down<c && maze[up][down]!='#' && maze[up][down]!='F')
{
count++;
flag++;
dfs(maze,up,down,count);
}
}
if(flag==0)
{
if(impossible == -1)
impossible = 1;
return;
}
}
Fancy

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11624 - Fire!

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm

### Re: 11624 - Fire!

Remove after update
Last edited by shuvokr on Tue Jun 25, 2013 6:12 pm, edited 3 times in total.

Code: Select all

``enjoying life ..... ``

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11624 - Fire!

Input:

Code: Select all

``````1
3 5
#####
#J.F#
##.##``````
AC output:

Code: Select all

``IMPOSSIBLE``
Check input and AC output for thousands of problems on uDebug!

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm

### Re: 11624 - Fire!

Code: Select all

``````Remove After Accepted
``````
Last edited by shuvokr on Sun Jun 30, 2013 1:59 pm, edited 2 times in total.

Code: Select all

``enjoying life ..... ``

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11624 - Fire!

Try input:

Code: Select all

``````2
4 4
####
#J.#
#..#
#..#
3 3
###
#J.
#..``````
Check input and AC output for thousands of problems on uDebug!

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm

### Re: 11624 - Fire!

Code: Select all

``````Remove after Accepted
``````
Last edited by shuvokr on Sun Jun 30, 2013 2:00 pm, edited 2 times in total.

Code: Select all

``enjoying life ..... ``

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11624 - Fire!

Running a full BFS for each fire square would be slow if there is a lot of fire. Try running a single BFS for all fire squares.
Check input and AC output for thousands of problems on uDebug!

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm

### Re: 11624 - Fire!

Code: Select all

``````Remove after Accepted
``````
Last edited by shuvokr on Sun Jun 30, 2013 2:01 pm, edited 3 times in total.

Code: Select all

``enjoying life ..... ``

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11624 - Fire!

Input:

Code: Select all

``````20
7 4
F..#
#.F.
F.F.
##..
FF##
FJFF
...F
3 3
#..
..#
J##
5 10
FF#F..FF#F
F..##F#FF.
#.F####F#F
F#F.##FJF#
#FF.##F#..
7 7
#.F.JF#
FF##.F.
FF.#F.F
.##.#F#
F#.#.F#
#F.FFF.
#FF#F##
6 9
#FF.F#.FF
.FF.F..F.
#.FF##F.#
..FFJ.FF#
.F.F.#.FF
####F...F
7 9
.####F#F#
#FFF.F.#F
FF.#F#F.#
#.FFF#F#.
F..F.#.J.
#.F#F.##F
F.#FF##F#
3 7
.JFF#F#
..F.#.F
F.##.#F
7 6
#.F###
.##.#F
F.J.##
FF#F##
.#..F.
#F..FF
F#FF#.
5 1
F
.
#
F
J
3 3
.#F
..F
FFJ
1 9
F##J.#.F.
10 10
#...F...F.
F..F##...F
F.###..###
##.F#..F##
.#F#F##FF.
..#FF.##F.
.F#J#.#F##
FF.FF.FF#.
.FF##FFF#.
FFF.F###F.
6 5
.#..F
F#F.#
FF##.
#F##F
FF###
#F##J
6 1
F
#
#
J
.
.
5 8
JFF..###
.F#.#.F.
##F...F.
#.FF##F.
#FFFF##.
7 9
F##..F#.F
#F#.FFF#.
.##.###.F
.F##F..##
....F....
.#.#FF.F#
FF.F..#J.
1 8
FF....J#
7 10
.####.##.F
###F.#.##F
.F.#F##F#F
F.#F#..#F#
.F.FF#F..#
#F#FJ#FF#F
F#FF#FFF.#
4 4
#J.F
#.#F
F.F#
#F##
10 6
.F.#F#
F#F.F.
F.###.
#FF###
#F.J.#
FF.F#.
#F..FF
##.F.#
#F###.
.#F#F.
``````
AC output:

Code: Select all

``````2
1
IMPOSSIBLE
1
IMPOSSIBLE
IMPOSSIBLE
1
IMPOSSIBLE
1
1
1
IMPOSSIBLE
1
1
1
1
1
IMPOSSIBLE
1
IMPOSSIBLE
``````
Last edited by brianfry713 on Sat Jun 29, 2013 3:06 am, edited 1 time in total.
Check input and AC output for thousands of problems on uDebug!

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm

### Re: 11624 - Fire!

match...
Last edited by shuvokr on Sat Jun 29, 2013 9:42 pm, edited 1 time in total.

Code: Select all

``enjoying life ..... ``

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11624 - Fire!

I edited the output in my previous post, it matches yours.

Here's how I solved this problem.
I first run BFS to calculate the minimum time it takes a square to catch on fire. I insert every initial F square into a queue and each of those takes time 0 to catch on fire.
I then run BFS starting from Joe. Joe can move if he can reach that square before it catches on fire. Calculate the earliest time Joe can make it out of the maze.
I use two different 1000 by 1000 int arrays to keep track of the minimum times it takes a square to catch on fire and the minimum time it takes Joe to reach a square.

Try to modify your code to match my algorithm.
Check input and AC output for thousands of problems on uDebug!

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm
``enjoying life ..... ``