11624 - Fire!

[shuvokr]

Code: Select all

Accepted  :D 

[brianfry713]

Input:

Code: Select all

1
4 4
####
#J.#
...#
..F#

Output should be 3

[holigan187]

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;

struct toado
{
    int h;
    int c;
};

toado huong[5]={ -1,0
                ,0,1
                ,1,0
                ,0,-1 };

toado q[1000009];
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]

Don't read and write to files.

[holigan187]

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

[Mukit Chowdhury]

Found my error...

[shuvokr]

Sample Input:
1
1 1
J

Your code's output:
IMPOSSIBLE
Is it right ?

Ac output:
1

[Mukit Chowdhury]

Sample Input:
1
1 1
J

Your code's output:
IMPOSSIBLE
Is it right ?

Ac output:
1

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

[shuvokr]

Input:
2
1 5
FFJFF
2 5
FFJFF
FFFFF

Ac output:
1
1

Your code's output:
IMPOSSIBLE
IMPOSSIBLE

[Mukit Chowdhury]

Input:
2
1 5
FFJFF
2 5
FFJFF
FFFFF

Ac output:
1
1

Your code's output:
IMPOSSIBLE
IMPOSSIBLE

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

[brianfry713]

holigan187, it looks like you figured it out.

[mahade hasan]

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]

[brianfry713]

Try input:

Code: Select all

1
4 4
####
#J.#
#..#
####

[walking_hell]

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]

Input:

Code: Select all

1
4 4
####
#J.#
#..#
#.##

Output should be 3