## 11624 - Fire!

Moderator: Board moderators

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

### Re: 11624 - Fire!

Code: Select all

``Accepted  :D ``

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
4 4
####
#J.#
...#
..F#
``````
Output should be 3
Check input and AC output for thousands of problems on uDebug!

holigan187
New poster
Posts: 3
Joined: Thu Aug 08, 2013 5:41 pm

### Re: 11624 - Fire!

Code: Select all

``````#include<iostream>
#include<fstream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define fi "fire.inp"
#define fo "fire.out"

using namespace std;

{
int h;
int c;
};

,0,1
,1,0
,0,-1 };

int nhang,ncot;
int itest,ntest;
long t[1111][1111];
char s[1111][1111];
long dau,cuoi;
int xph,xpc;
int sida;
long kq;

void input()
{
int i,j;

scanf("%d %d\n",&nhang,&ncot);

dau=-1;
cuoi=-1;

for (i=0;i<nhang;i++)
{
gets(s[i]);
for (j=0;j<ncot;j++)
{
t[i][j]=0;

if ( s[i][j] == 'F' )
{
cuoi++;
q[cuoi].h=i;
q[cuoi].c=j;
}
else
{
if ( s[i][j] == 'J' )
{
xph=i;
xpc=j;
}
}
}
}
}

void loang()
{
int hd,cd,hc,cc;
int i;

if ( xph == 0 || xph == nhang-1 || xpc == 0 || xpc == ncot-1 )
{
sida=1;
kq=1;
return;
}
cuoi++;
q[cuoi].h=xph;
q[cuoi].c=xpc;
t[xph][xpc]=1;

while ( dau < cuoi )
{
dau++;
hd=q[dau].h;
cd=q[dau].c;

for (i=0;i<4;i++)
{
hc=hd+huong[i].h;
cc=cd+huong[i].c;

if ( t[hd][cd] == 0 )       //lua
{
if ( s[hc][cc] == '.' && hc >= 0 && hc < nhang && cc >=0 && cc < ncot )
{
s[hc][cc] = 'F';
cuoi++;
q[cuoi].h=hc;
q[cuoi].c=cc;
}
}
else                        //john
{
if ( s[hc][cc] == '.')
{
s[hc][cc] = 'J';
cuoi++;
q[cuoi].h=hc;
q[cuoi].c=cc;
t[hc][cc]=t[hd][cd]+1;

if ( hc == 0 || hc == nhang-1 || cc == 0 || cc == ncot-1 )
{
sida=1;
kq=t[hc][cc];
return;
}
}
}
}
}
}

void solve()
{
sida=0;
loang();
}

void output()
{
if ( sida == 1 )
printf("%ld\n",kq);
else
printf("IMPOSSIBLE\n");
}

int main()
{
freopen(fi,"r",stdin);
freopen(fo,"w",stdout);

scanf("%d",&ntest);
gets(s[0]);

for (itest=0;itest<ntest;itest++)
{
input();
solve();
output();
}

return 0;
}
``````
someone plz help me, i use BFS but still RTE time by time,i check many many times already =((
someone tell me where is my bug =((

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

### Re: 11624 - Fire!

Don't read and write to files.
Check input and AC output for thousands of problems on uDebug!

holigan187
New poster
Posts: 3
Joined: Thu Aug 08, 2013 5:41 pm

### Re: 11624 - Fire!

i know it, i alway delete it when i submit,its not problem

Mukit Chowdhury
Learning poster
Posts: 99
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 11624 - Fire!

Found my error...
Last edited by Mukit Chowdhury on Mon Sep 16, 2013 7:31 pm, edited 1 time in total.

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

### Re: 11624 - Fire!

Sample Input:
1
1 1
J

IMPOSSIBLE
Is it right ?

Ac output:
1

Code: Select all

``enjoying life ..... ``

Mukit Chowdhury
Learning poster
Posts: 99
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 11624 - Fire!

shuvokr wrote:Sample Input:
1
1 1
J

IMPOSSIBLE
Is it right ?

Ac output:
1
But my compiler prints 1 for your input... I use microsoft visual c++ 6.0

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

### Re: 11624 - Fire!

Input:
2
1 5
FFJFF
2 5
FFJFF
FFFFF

Ac output:
1
1

IMPOSSIBLE
IMPOSSIBLE

Code: Select all

``enjoying life ..... ``

Mukit Chowdhury
Learning poster
Posts: 99
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 11624 - Fire!

shuvokr wrote:Input:
2
1 5
FFJFF
2 5
FFJFF
FFFFF

Ac output:
1
1

IMPOSSIBLE
IMPOSSIBLE
How funny !!! my code prints 1 for both case in my compiler !!!

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

### Re: 11624 - Fire!

holigan187, it looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!

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

### Re: 11624 - Fire!

still TLE
TLE TLE TLe ....help need

Code: Select all

``````#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef queue<pair<int,int> >Queue;
int Fire[1010][1010],Joe[1010][1010],R,C;
char Input[1010][1010];
pair<int,int> Pair;

void Cal(Queue F){

int I,K,L;
while(!F.empty()){
Pair=F.front();
F.pop();
I=Pair.first;
K=Pair.second;

if(I-1>0&&Input[I-1][K]!='#'&&Fire[I-1][K]>Fire[I][K]+1){
Fire[I-1][K]=Fire[I][K]+1;
F.push(make_pair(I-1,K));
}
if(I+1<=R&&Input[I+1][K]!='#'&&Fire[I+1][K]>Fire[I][K]+1){
Fire[I+1][K]=Fire[I][K]+1;
F.push(make_pair(I+1,K));
}
if(K-1>0&&Input[I][K-1]!='#'&&Fire[I][K-1]>Fire[I][K]+1){
Fire[I][K-1]=Fire[I][K]+1;
F.push(make_pair(I,K-1));
}
if(K+1<=C&&Input[I][K+1]!='#'&&Fire[I][K+1]>Fire[I][K]+1){
Fire[I][K+1]=Fire[I][K]+1;
F.push(make_pair(I,K+1));
}
}
}

int main()
{
int I,K,L,M,N,Tcase;

scanf("%d",&Tcase);
while(Tcase--){
scanf("%d %d",&R,&C);
//getchar();
Queue F,J;
for(I=1;I<=R;I++)
for(K=1;K<=C;K++){
Joe[I][K]=30000;
Fire[I][K]=30000;
scanf("\n");
scanf("%c",&Input[I][K]);
if(Input[I][K]=='F'){
F.push(make_pair(I,K));
Fire[I][K]=0;
}
else if(Input[I][K]=='J'){
J.push(make_pair(I,K));
Joe[I][K]=0;
}
}
//printf("%d %d\n",R,C);

if(!F.empty()){
Cal(F);
}
bool Flag=0;
while(!J.empty()){
Pair=J.front();
J.pop();
I=Pair.first;
K=Pair.second;

//printf("%d %d\n",I,K);

if(I==1||I==R||K==1||K==C){
Flag=true;
break;
}

if(I-1>0&&Input[I-1][K]!='#'&&Joe[I][K]+1<Fire[I-1][K]){
Joe[I-1][K]=Joe[I][K]+1;
J.push(make_pair(I-1,K));
}
if(I+1<=R&&Input[I+1][K]!='#'&&Joe[I][K]+1<Fire[I+1][K]){
Joe[I+1][K]=Joe[I][K]+1;
J.push(make_pair(I+1,K));
}
if(K-1>0&&Input[I][K-1]!='#'&&Joe[I][K]+1<Fire[I][K-1]){
Joe[I][K-1]=Joe[I][K]+1;
J.push(make_pair(I,K-1));
}
if(K+1<=C&&Input[I][K+1]!='#'&&Joe[I][K]+1<Fire[I][K+1]){
Joe[I][K+1]=Joe[I][K]+1;
J.push(make_pair(I,K+1));
}
}
if(Flag){
printf("%d\n",Joe[I][K]+1);
}
else
printf("IMPOSSIBLE\n");
}
return 0;
}

``````
[/color]
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 input:

Code: Select all

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

walking_hell
New poster
Posts: 14
Joined: Tue Sep 24, 2013 4:35 pm

### uva 11624

why wa ???

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<fstream>
#include<cstring>
using namespace std;
char field[1010][1010];
int dist;
int row,col;
bool bfs()
{

queue <int>J,f;
bool res=false;

int distf[row+6][col+6],distj[row+6][col+6];

for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
distf[i][j]=0;
distj[i][j]=0;
if(field[i][j]=='F')
{f.push(i);f.push(j);}
if(field[i][j]=='J')
{J.push(i);J.push(j);}

}
}

while(!f.empty())
{

int i=f.front();

f.pop();
int j=f.front();
f.pop();
//cout<<i<<" "<<j<<" "<<" "<<distf[i][j]<<endl;
for(int l=-1;l<=1;l++)
{
for(int m=-1;m<=1;m++)
{
if((l==-1&&m==-1)||(l==1&&m==1)||(l==-1&&m==1)||(l==1&&m==-1)||(l==0 &&m==0))
continue;
if(l+i>=row||l+i<0||m+j>=col||m+j<0)
{
continue;
}
if(field[l+i][m+j]!='#'&&field[l+i][m+j]!='F')
{distf[l+i][m+j]=distf[i][j]+1;
field[l+i][m+j]='F';
f.push(l+i);
f.push(m+j);}
}
}
}
int flag=0;
//cout<<"hlw";
while(!J.empty())
{
int i=J.front();
J.pop();
int j=J.front();
J.pop();

//field[i][j]='J';
for(int l=-1;l<=1;l++)
{
for(int m=-1;m<=1;m++)
{
if((l==-1&&m==-1)||(l==1&&m==1)||(l==-1&&m==1)||(l==1&&m==-1)||(l==0 &&m==0))
continue;
if(l+i>=row||l+i<0||m+j>=col||m+j<0)
{
if((distj[i][j]<distf[i][j]) || (distf[i][j]==0&&distj[i][j]==0))
{
if(flag==0)
{
flag=1;
dist=distj[i][j]+1;
res=true;
}
else
{
if(distj[i][j]+1 <dist)
dist=distj[i][j]+1;

}
}
continue;
}
if(field[l+i][m+j]!='#'&&field[l+i][m+j]!='J')
{distj[l+i][m+j]=distj[i][j]+1;
field[l+i][m+j]='J';
J.push(l+i);
J.push(m+j);}
}
}
}
return res;
}
int main()
{
int tst;

//freopen("/media/Others/input.txt","r",stdin);
scanf("%d",&tst);
for(int i=0;i<tst;i++)
{
scanf("%d%d",&row,&col);
for(int i=0;i<row;i++)
{
scanf("%s",field[i]);
}
//int jx=-1,jy=-1,fx=-1,fy=-1;

bool res=bfs();

if(res==false)
printf("IMPOSSIBLE\n");
else
printf("%d\n",dist);
}
return 0;
}
``````

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

### Re: uva 11624

Input:

Code: Select all

``````1
4 4
####
#J.#
#..#
#.##
``````
Output should be 3
Check input and AC output for thousands of problems on uDebug!