UVA11624 TLE 求调,悬赏关注!!!
查看原帖
UVA11624 TLE 求调,悬赏关注!!!
797354
Ferdina_zcjb楼主2023/8/17 09:29
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 1001;
int wayx[] = {0,1,-1,0,0},wayy[]={0,0,0,1,-1};

char G[MAX][MAX];
int r,c,vis[MAX][MAX];
int mx,my;

struct node{
	int ti,x,y;
	bool friend operator < (node a,node b){
		return a.ti > b.ti;
	}
};

struct no{
    int me,tx,ty;
};
queue<no> qp; 

struct on_it{
	char val;
	int tei;
};
on_it g[MAX][MAX];

void bff(void){
	memset(vis,0,sizeof(vis));
	while(!qp.empty()){
		no now = qp.front();
		//cout << now.tx << " " << now.ty << endl; 
		qp.pop();
		if (g[now.tx][now.ty].val != 'F'){
			g[now.tx][now.ty].val = 'F';
			g[now.tx][now.ty].tei = now.me ;
		}
		if(now.tx < 1 || now.tx > r || now.ty < 1 || now.ty > c)continue;
		
		for(int i = 1;i <= 4;++i){
			int xx = now.tx + wayx[i];
			int yy = now.ty + wayy[i];
			
			if(G[xx][yy] == '#' || g[xx][yy].val == 'F')continue;
			
			qp.push((no){now.me+1,xx,yy});
		}
	}
}
int bfs(void){
	priority_queue<node> q;
	q.push((node){0,mx,my});
	
	while(!q.empty()){
		node now = q.top();
		//node now = q.front();
		q.pop();
		
		if(now.x < 1 || now.x > r || now.y < 1 || now.y > c){
		    return now.ti;
		}
		
		for(int i = 1;i <= 4;++i){
		    int xx = now.x+wayx[i];
		    int yy = now.y+wayy[i];
		    //cout << xx << " " << yy << " " << now.ti+1 << endl;
		    if((g[xx][yy].val == 'F'&&g[xx][yy].tei <= now.ti+1) || G[xx][yy] == '#')continue;
		    
			q.push((node){now.ti+1,xx,yy});
		}
	}
	return -1;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    int T;
    cin >> T;
    
	while(T--){
		
		while(!qp.empty())qp.pop();
		
        cin >> r >> c;
        
		for(int i = 1;i <= r;++i){
			for(int j = 1;j <= c;++j){
				g[i][j].val = '.';
				cin >> G[i][j];
				
				if(G[i][j] == 'J'){
					mx = i;
					my = j;
				}else if(G[i][j] == 'F'){
					qp.push((no){0,i,j});
				}
			}
		}
		
		bff();
		int ans = bfs();
		
		if(ans == -1){
			cout << "IMPOSSIBLE\n";
		}else{
			cout << ans << "\n";
		}
	}
} 
2023/8/17 09:29
加载中...