Code: Select all
Accepted :D
Moderator: Board moderators
Code: Select all
1
4 4
####
#J.#
...#
..F#
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;
}
Code: Select all
enjoying life .....
But my compiler prints 1 for your input... I use microsoft visual c++ 6.0shuvokr wrote:Sample Input:
1
1 1
J
Your code's output:
IMPOSSIBLE
Is it right ?![]()
Ac output:
1
Code: Select all
enjoying life .....
How funny !!! my code prints 1 for both case in my compiler !!!shuvokr wrote:Input:
2
1 5
FFJFF
2 5
FFJFF
FFFFF
Ac output:
1
1
Your code's output:
IMPOSSIBLE
IMPOSSIBLE
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;
}
Code: Select all
1
4 4
####
#J.#
#..#
####
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;
}
Code: Select all
1
4 4
####
#J.#
#..#
#.##