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

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 11624 - Fire!

Post by mahade hasan » Sat Sep 15, 2012 4:38 pm

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!

Post by brianfry713 » Wed Sep 19, 2012 1:47 am

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!

Post by Sabiha_Fancy » Sun Mar 17, 2013 10:47 pm

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!

Post by brianfry713 » Tue Mar 19, 2013 10:10 pm

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
Location: Bangladesh

Re: 11624 - Fire!

Post by shuvokr » Mon Jun 24, 2013 10:14 pm

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!

Post by brianfry713 » Tue Jun 25, 2013 1:02 am

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
Location: Bangladesh

Re: 11624 - Fire!

Post by shuvokr » Tue Jun 25, 2013 6:11 pm

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!

Post by brianfry713 » Tue Jun 25, 2013 11:26 pm

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
Location: Bangladesh

Re: 11624 - Fire!

Post by shuvokr » Sat Jun 29, 2013 12:10 am

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!

Post by brianfry713 » Sat Jun 29, 2013 12:32 am

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
Location: Bangladesh

Re: 11624 - Fire!

Post by shuvokr » Sat Jun 29, 2013 1:09 am

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!

Post by brianfry713 » Sat Jun 29, 2013 1:32 am

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
Location: Bangladesh

Re: 11624 - Fire!

Post by shuvokr » Sat Jun 29, 2013 2:18 am

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!

Post by brianfry713 » Sat Jun 29, 2013 3:28 am

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
Location: Bangladesh

Re: 11624 - Fire!

Post by shuvokr » Sat Jun 29, 2013 9:41 pm

Thanks brianfry713
Last edited by shuvokr on Sun Jun 30, 2013 2:01 pm, edited 2 times in total.

Code: Select all

enjoying life ..... 

Post Reply

Return to “Volume 116 (11600-11699)”