WA求助
  • 板块UVA11624 Fire!
  • 楼主Moeebius
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/10/6 21:05
  • 上次更新2023/11/4 04:31:30
查看原帖
WA求助
356003
Moeebius楼主2021/10/6 21:05
#include<bits/stdc++.h>
using namespace std;
int T,n,m;
char a[1003][1003];
int t[1003][1003];
struct point
{
	int x,y,step;
}q[10000001],s;
int front,tail;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
bool used[1001][1001];

void gettime()
{
	while(front<=tail)
	{
		point u=q[front++];
		point v;
		for(int i=0; i<4; i++)
		{
			v.x=u.x+dx[i],v.y=u.y+dy[i],v.step=u.step+1;
            
			if(v.x<1 || v.x>n || v.y<1 || v.y>m) continue;
			if(a[v.x][v.y]=='#') continue;
            
			if(used[v.x][v.y]) continue;
            //cout<<v.x<<' '<<v.y<<' '<<v.step<<endl;
			t[v.x][v.y]=v.step;
			q[++tail]=v;
			used[v.x][v.y]=1;
		}
	}
}

int main(int argc, char const *argv[])
{
	
	cin>>T;

	while(T--)
	{
	    front=1,tail=0;
        memset(used,0,sizeof(used));
        memset(t,-1,sizeof(t));
		scanf("%d %d",&n,&m);
		for(int i=1; i<=n; i++)
		{
			scanf("%s",a[i]+1);
			for(int j=1; j<=m; j++)
			{
				if(a[i][j]=='F')
				{
					q[++tail]=(point){i,j,0};
					t[i][j]=0;
                    used[i][j]=1;
				}
				else if(a[i][j]=='J')
					s.x=i,s.y=j,s.step=0;
			}
		}
		gettime();//火
        if(s.x==n || s.y==m || s.x==1 || s.y==1) {
            cout<<0;
            continue;
        }//起点即终点
        //人
		front=tail=1;
		q[1]=s;
		memset(used,0,sizeof(used));
		//cout<<"BEGIN\n";
        bool flg=0;
		while(front<=tail)
		{
			point u=q[front++];
			point v;
			for(int i=0; i<4; i++)
			{
				v.x=u.x+dx[i],v.y=u.y+dy[i],v.step=u.step+1;
				if(v.x<1 || v.x>n || v.y<1 || v.y>m) continue;
				if(a[v.x][v.y]=='#') continue;
				if(t[v.x][v.y]<=v.step && t[v.x][v.y]!=-1) continue;
				if(used[v.x][v.y]) continue;
				if(v.x==n || v.y==m || v.x==1 || v.y==1)
				{
					cout<<v.step+1<<endl;
                    flg=1;
					goto end;
				}
				q[++tail]=v;
				used[v.x][v.y]=1;
			}
		}
        end:
		if(flg==0)cout<<"IMPOSSIBLE\n";
	}
	return 0;
}
2021/10/6 21:05
加载中...