11624 - Fire!

[mahade hasan]

TLE continue ...

[brianfry713]

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.

[Sabiha_Fancy]

I am getting wa. Help me

Here is my code

Code: Select all

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

[brianfry713]

Doesn't match the sample I/O.

[shuvokr]

Remove after update

[brianfry713]

Input:

Code: Select all

1
3 5
#####
#J.F#
##.##

AC output:

Code: Select all

IMPOSSIBLE

[shuvokr]

Code: Select all

Remove After Accepted

[brianfry713]

Try input:

Code: Select all

2
4 4
####
#J.#
#..#
#..#
3 3
###
#J.
#..

[shuvokr]

Code: Select all

Remove after Accepted

[brianfry713]

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.

[shuvokr]

Code: Select all

Remove after Accepted

[brianfry713]

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

[shuvokr]

match...

[brianfry713]

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.

[shuvokr]

Thanks brianfry713