11624 - Fire!
Moderator: Board moderators
-
- Learning poster
- Posts: 76
- Joined: Mon Jul 21, 2008 8:50 am
- Location: SUST,SYLHET,BANGLADESH.
- Contact:
11624 - Fire!
AC
Last edited by calicratis19 on Wed Nov 18, 2009 7:47 pm, edited 1 time in total.
Heal The World
Re: 11624 - Fire!
Hi calicratis19,
I think, that the reason of RTE may be here:
and then
Think about case, when the maze has 1000 rows, 1000 columns and here is one "J" and 999999 "F". Array array should have length 1999998 (or little bit more - for insure). Think about length of other arrays in your program too. If the length is too short, it causes RTE.
Hope it helps and you will get AC now![:)](./images/smilies/icon_smile.gif)
I think, that the reason of RTE may be here:
Code: Select all
array[1103]
Code: Select all
else if(cha=='F')
{
array[y]=i;
array[y+1]=j;
y+=2;
Adjacent [ i ][ j ] = 1;
}
Hope it helps and you will get AC now
![:)](./images/smilies/icon_smile.gif)
-
- Learning poster
- Posts: 76
- Joined: Mon Jul 21, 2008 8:50 am
- Location: SUST,SYLHET,BANGLADESH.
- Contact:
Re: 11624 - Fire!
sorry that i havent edited my code . i have noticed the mistake that u have pointed here. i already changed my array size.but its wa now. can u pls tell me why wa now. thanks for your reply.
Heal The World
Re: 11624 - Fire!
Try to think how to solve this problem with one BFS!!!
Re: 11624 - Fire!
As Igor9669 wrote, one BFS is enough. In each step of BFS, at first "extend" the fire () and at second "extend" the move of Joe. I don't understand your implementation clearly, I used three 2-dimensional array, one for reading input, one for movement of Joe and one for extension of fire.
Re: 11624 - Fire!
I try run your program and I think, that I found some wrong outputs.
For example, for input:
your program returns
but correct output is
So, try to fix it, or think about only one BFS, or another implementation. Hope you will get AC now ![:)](./images/smilies/icon_smile.gif)
For example, for input:
Code: Select all
5
1 1
J
1 2
J.
2 1
.
J
2 2
..
.J
2 2
..
FJ
Code: Select all
IMPOSSIBLE
2
2
2
2
Code: Select all
1
1
1
1
1
![:)](./images/smilies/icon_smile.gif)
-
- Learning poster
- Posts: 76
- Joined: Mon Jul 21, 2008 8:50 am
- Location: SUST,SYLHET,BANGLADESH.
- Contact:
Re: 11624 - Fire!
hi everyone,i am getting run time error a lot in this prob.
could anyone check my code to tell the cause of wa.
//code here
#include<stdio.h>
#include<stdlib.h>
#define inf 100000
int fire[1005][1005],min;
char input[1005][1005];
int row,col,que[1000005][3],r[]={0,0,-1,1},c[]={-1,1,0,0};
void BFS(int rr,int cc,int var);
int main()
{
int test,i,j,m,n;
scanf("%d",&test);
while(test--)
{
scanf("%d %d",&row,&col);
for(i=0;i<row;i++)
scanf("%s",input);
for(i=0;i<row;i++)
for(j=0;j<row;j++)
fire[j]=inf;
for(i=0;i<row;i++)
for(j=0;j<row;j++)
{
if(input[j]=='F')
{
BFS(i,j,1);
}
if(input[j]=='J')
{
m=i;n=j;
}
}
/*for(i=0;i<row;i++){
for(j=0;j<col;j++)
printf("%d ",fire[j]);
printf("\n");
}*/
min=inf;
BFS(m,n,0);
if(min==inf)
printf("IMPOSSIBLE\n");
else printf("%d\n",min);
}
return 0;
}
void BFS(int rr,int cc,int var)
{
int i,m,n,front,rear;
if(var) fire[rr][cc]=0;
else if(rr==0||rr==row-1||cc==0||cc==col-1)
{ min=1;return;}
front=rear=0;
que[rear][0]=rr;
que[rear][1]=cc;
que[rear][2]=0;
rear++;
while(front!=rear)
{
for(i=0;i<4;i++)
{
m=que[front][0]+r;
n=que[front][1]+c;
if((m>=0&&m<row)&&(n>=0&&n<col))
if( input[m][n]!='#' && que[front][2]+1<fire[m][n])
{
que[rear][0]=m;
que[rear][1]=n;
que[rear++][2]=que[front][2]+1;
if(var)
fire[m][n]=que[front][2]+1;
else if(m==0||m==row-1||n==0||n==col-1)
{
if(que[front][2]+2<min)
min=que[front][2]+2;
}
}
}
front++;
}
}
could anyone check my code to tell the cause of wa.
//code here
#include<stdio.h>
#include<stdlib.h>
#define inf 100000
int fire[1005][1005],min;
char input[1005][1005];
int row,col,que[1000005][3],r[]={0,0,-1,1},c[]={-1,1,0,0};
void BFS(int rr,int cc,int var);
int main()
{
int test,i,j,m,n;
scanf("%d",&test);
while(test--)
{
scanf("%d %d",&row,&col);
for(i=0;i<row;i++)
scanf("%s",input);
for(i=0;i<row;i++)
for(j=0;j<row;j++)
fire[j]=inf;
for(i=0;i<row;i++)
for(j=0;j<row;j++)
{
if(input[j]=='F')
{
BFS(i,j,1);
}
if(input[j]=='J')
{
m=i;n=j;
}
}
/*for(i=0;i<row;i++){
for(j=0;j<col;j++)
printf("%d ",fire[j]);
printf("\n");
}*/
min=inf;
BFS(m,n,0);
if(min==inf)
printf("IMPOSSIBLE\n");
else printf("%d\n",min);
}
return 0;
}
void BFS(int rr,int cc,int var)
{
int i,m,n,front,rear;
if(var) fire[rr][cc]=0;
else if(rr==0||rr==row-1||cc==0||cc==col-1)
{ min=1;return;}
front=rear=0;
que[rear][0]=rr;
que[rear][1]=cc;
que[rear][2]=0;
rear++;
while(front!=rear)
{
for(i=0;i<4;i++)
{
m=que[front][0]+r;
n=que[front][1]+c;
if((m>=0&&m<row)&&(n>=0&&n<col))
if( input[m][n]!='#' && que[front][2]+1<fire[m][n])
{
que[rear][0]=m;
que[rear][1]=n;
que[rear++][2]=que[front][2]+1;
if(var)
fire[m][n]=que[front][2]+1;
else if(m==0||m==row-1||n==0||n==col-1)
{
if(que[front][2]+2<min)
min=que[front][2]+2;
}
}
}
front++;
}
}
why i got RTE in fire 11624
Code: Select all
#include <stdio.h>
#include <string.h>
#define inf 99999999
#define sz 1100
#define SZ 1100110
long r[]={0,0,-1,1},c[]={-1,1,0,0},dist_joe[sz][sz],dist_fire[sz][sz];
long cur_x,cur_y,que_x[SZ],que_y[SZ],head,tail;
long m,n,test,row,col,i,j,no_fire,joe_x,joe_y,cost;
char array[sz][sz];
void bfs_fire(int x,int y)
{
int i;
head = tail = 0; que_x[tail]=x; que_y[tail++]=y; dist_fire[x][y]=1;
while(head != tail)
{
cur_x=que_x[head]; cur_y=que_y[head++];
for(i=0;i<4;++i)
{
m=cur_x+r[i]; n=cur_y+c[i];
if(m<0 || n<0 || m>=row || n>=col)
continue;
if( array[m][n]=='.' && dist_fire[cur_x][cur_y]+1 < dist_fire[m][n])
{
dist_fire[m][n]=dist_fire[cur_x][cur_y]+1;
que_x[tail]=m; que_y[tail++]=n;
}
}
}
}
void bfs_joe(int x,int y)
{
int i;
head = tail = 0; que_x[tail]=x; que_y[tail++]=y; dist_joe[x][y]=1;
while(head != tail)
{
cur_x=que_x[head]; cur_y=que_y[head++];
for(i=0;i<4;++i)
{
m=cur_x+r[i]; n=cur_y+c[i];
if(m<0 || n<0 || m>=row || n>=col)
continue;
if( array[m][n]=='.' && dist_joe[cur_x][cur_y]+1 < dist_fire[m][n])
{
array[m][n]='#';
dist_joe[m][n]=dist_joe[cur_x][cur_y]+1;
que_x[tail]=m; que_y[tail++]=n;
}
}
}
}
int main()
{
scanf("%ld",&test);
while(test--)
{
scanf("%ld %ld",&row,&col);
for(i=0;i<row;++i)
scanf("%s",array[i]);
for(i=0;i<=row;i++)
for(j=0;j<=col;j++)
dist_fire[i][j]=dist_joe[i][j]=inf;
for(i=0;i<row;++i)
for(j=0;j<col;++j)
{
if(array[i][j]=='J')
joe_x=i , joe_y=j;
if(array[i][j]=='F')
bfs_fire(i,j);
}
bfs_joe(joe_x,joe_y);
cost=inf;
for(i=0;i<row;++i)
for(j=0;j<col;++j)
{
if((i==0 || j==0 || i==row-1 || j==col-1) && dist_joe[i][j] < cost )
cost=dist_joe[i][j];
}
if(cost==inf)
printf("IMPOSSIBLE\n");
else
printf("%ld\n",cost);
}
return 0;
}
Re: 11624 - Fire!
Ur code and logic is ok .
U can speedup it by returning ur answer from j_bfs but not cheacking in main.
Ur code got accepted when I use int against long.
Becos u know may be assigning long array or initialising takes more time here.
Good regards Friend.![:lol:](./images/smilies/icon_lol.gif)
U can speedup it by returning ur answer from j_bfs but not cheacking in main.
Ur code got accepted when I use int against long.
Becos u know may be assigning long array or initialising takes more time here.
Good regards Friend.
![:lol:](./images/smilies/icon_lol.gif)
Re: 11624 - Fire!
thank u frnd i became foolish when i got accepted after changing data type int instead of long
-
- New poster
- Posts: 22
- Joined: Tue Jul 20, 2010 9:55 pm
Re: 11624 - Fire!
getting WA! please help! thanks in advance
Code: Select all
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAX 1010
using namespace std;
int r,c;
char grid[MAX][MAX];
bool flag=false;
struct Node{
int x;
int y;
};
int dj[MAX][MAX];
int arr[]={-1,0,1,0,0,-1,0,1};
void bfs(Node s,Node y)
{
queue<Node> f;
queue <Node> j;
dj[s.x][s.y]=1;
j.push(s);
f.push(y);
int u,v;
while(!j.empty())
{
Node tmp=j.front();j.pop();
if(grid[tmp.x][tmp.y]!='F') //for J
{
for(int i=0;i<8;i+=2)
{
int row=tmp.x+arr[i];
int col=tmp.y+arr[i+1];
if(row>=0 && row<r && col>=0 && col<c )
{
if(grid[row][col]=='.')
{
Node t; t.x=row; t.y=col;
j.push(t);
dj[row][col]=dj[tmp.x][tmp.y]+1;
grid[row][col]='J';
}
}
else //if in last or first row or column
{
//cout<<tmp.x<<" "<<tmp.y<<" "<<dj[tmp.x][tmp.y]<<endl;
cout<<dj[tmp.x][tmp.y]<<endl;
flag=true; return;
u=tmp.x;
v=tmp.y;
}
}
}
if(!j.empty()) //for fire
{
tmp=f.front();f.pop();
for(int i=0;i<8;i+=2)
{
int row=tmp.x+arr[i];
int col=tmp.y+arr[i+1];
if(row>=0 && row<r && col>=0 && col<c )
{
if(grid[row][col]=='.'|| grid[row][col]=='J')
{
Node t; t.x=row;
t.y=col; f.push(t);
grid[row][col]='F';
}
}
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
for(int m=0;m<t;m++)
{
scanf("%d%d",&r,&c);
for(int i=0;i<r;i++)
scanf("%s",grid[i]);
Node s,y;
s.x=-1;
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
{
if(grid[i][j]=='J')
s.x=i,s.y=j;
else if(grid[i][j]=='F')
y.x=i,y.y=j;
}
flag=false;
if(s.x!=-1)
bfs(s,y);
if(!flag)
printf("IMPOSSIBLE\n");
}
return 0;
}
-
- Experienced poster
- Posts: 147
- Joined: Mon Jun 07, 2010 11:43 am
- Location: University Of Dhaka,Bangladesh
- Contact:
Re: 11624 - Fire!
I solved the problem running two Breadth First Search at a time. First check where fire can go from initial positions then check where Joe can go. assign current position to initial position and repeat the steps until joe reach safety point,thats is on the edge of the matrix. If joe has no where to go then print IMPOSSIBLE. check this I/O:
output:
you should get ac now
.
happy programing
Code: Select all
4
10 10
##########
#.....JFF#
#........#
#........#
#........#
#........#
#........#
#........#
#........#
..########
3 1
#
J
F
1 2
.J
5 5
#####
#..F#
#.J.#
....F
#####
Code: Select all
14
1
1
4
![:wink:](./images/smilies/icon_wink.gif)
happy programing
UVa stats: http://felix-halim.net/uva/hunting.php?id=63448
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
-
- New poster
- Posts: 1
- Joined: Sun Nov 06, 2011 3:48 am
Re: 11624 - Fire!
Hey all i am getting RTE in FIRE 11624.. .. ?? would be helped a lot if any one can take me out of this bad situation .. thanks in advanced ::-::-::-
Code: Select all
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int mani(int a,int b){
return a<b?a:b;
}
struct node{
int u,v;
}temp,joe;
vector<node>fires;
int n,m;
string grid[1010];
int movex[]={0,0,1,-1};
int movey[]={1,-1,0,0};
bool visit[1010][1010];
int len[1010][1010],len1[1010][1010];
queue<node>q;
void BFS_FIRE(node start,bool hat){
// cout<<"okp"<<endl;
for(int j=0;j<n;j++){
for(int k=0;k<m;k++)visit[j][k]=false;
}
visit[start.u][start.v]=true;
if(hat==true)len[start.u][start.v]=0;
else len1[start.u][start.v]=0;
q.push(start);
while(!q.empty()){
temp=q.front();
q.pop();
for(int i=0;i<4;i++){
node lol;
lol.u=temp.u+movex[i];
lol.v=temp.v+movey[i];
if(hat==true){
if(grid[lol.u][lol.v]!='#'&&visit[lol.u][lol.v]==false&&len[lol.u][lol.v]>len[temp.u][temp.v]+1&&(lol.u>=0&&lol.u<n)&&(lol.v>=0&&lol.v<m)){
visit[lol.u][lol.v]=true;
len[lol.u][lol.v]=len[temp.u][temp.v]+1;
q.push(lol);
}
}
else {
if(grid[lol.u][lol.v]!='#'&&visit[lol.u][lol.v]==false&&(lol.u>=0&&lol.u<n)&&(lol.v>=0&&lol.v<m)){
visit[lol.u][lol.v]=true;
len1[lol.u][lol.v]=len1[temp.u][temp.v]+1;
q.push(lol);
}
}
}
}
}
int main()
{
freopen("sam.txt","r",stdin);
int i,t,j,k;
cin>>t;
for(i=0;i<t;i++){
cin>>n>>m;
for(j=0;j<n;j++)cin>>grid[j];
for(j=0;j<n;j++){
for(k=0;k<m;k++){
if(grid[j][k]=='J'){
joe.u=j;
joe.v=k;
}
if(grid[j][k]=='F'){
temp.u=j;
temp.v=k;
fires.push_back(temp);
}
}
}
for(j=0;j<n;j++){
for(k=0;k<m;k++)len[j][k]=len1[j][k]=1000;
}
for(j=0;j<fires.size();j++)BFS_FIRE(fires[j],true);
BFS_FIRE(joe,false);
int mini=1000;
for(j=0;j<m;j++){
if(len1[0][j]<len[0][j])mini=mani(mini,len1[0][j]);
}
for(j=0;j<m;j++){
if(len1[n-1][j]<len[n-1][j])mini=mani(mini,len1[n-1][j]);
}
for(j=0;j<n;j++){
if(len1[j][0]<len[j][0])mini=mani(mini,len1[j][0]);
}
for(j=0;j<n;j++){
if(len1[j][m-1]<len[j][m-1])mini=mani(mini,len1[j][m-1]);
}
if(mini==1000)cout<<"IMPOSSIBLE"<<endl;
else cout<<mini+1<<endl;
fires.clear();
}
return 0;
}
Re: 11624 - Fire!
i used one BFS more specifically Multi SSSP whit floodfill for memory saving in java, is a great problem to solve
. And also a simple self implemented queue that was help from a friend.
![:)](./images/smilies/icon_smile.gif)
Code: Select all
removed after AC.