Page 2 of 4
Re: 11624 - Fire!
Posted: Sat Sep 15, 2012 4:38 pm
by mahade hasan
TLE continue ...
Re: 11624 - Fire!
Posted: Wed Sep 19, 2012 1:47 am
by 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.
Re: 11624 - Fire!
Posted: Sun Mar 17, 2013 10:47 pm
by Sabiha_Fancy
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;
}
}
Re: 11624 - Fire!
Posted: Tue Mar 19, 2013 10:10 pm
by brianfry713
Doesn't match the sample I/O.
Re: 11624 - Fire!
Posted: Mon Jun 24, 2013 10:14 pm
by shuvokr
Remove after update
Re: 11624 - Fire!
Posted: Tue Jun 25, 2013 1:02 am
by brianfry713
Re: 11624 - Fire!
Posted: Tue Jun 25, 2013 6:11 pm
by shuvokr
Re: 11624 - Fire!
Posted: Tue Jun 25, 2013 11:26 pm
by brianfry713
Try input:
Code: Select all
2
4 4
####
#J.#
#..#
#..#
3 3
###
#J.
#..
Re: 11624 - Fire!
Posted: Sat Jun 29, 2013 12:10 am
by shuvokr
Re: 11624 - Fire!
Posted: Sat Jun 29, 2013 12:32 am
by 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.
Re: 11624 - Fire!
Posted: Sat Jun 29, 2013 1:09 am
by shuvokr
Re: 11624 - Fire!
Posted: Sat Jun 29, 2013 1:32 am
by 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
Re: 11624 - Fire!
Posted: Sat Jun 29, 2013 2:18 am
by shuvokr
match...
Re: 11624 - Fire!
Posted: Sat Jun 29, 2013 3:28 am
by 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.
Re: 11624 - Fire!
Posted: Sat Jun 29, 2013 9:41 pm
by shuvokr
Thanks brianfry713