PIPI的生化危机

题目描述：

浣熊市爆发了生化危机，PIPI作为上班迟到的一名新警察，被困在警察局了，他希望能从警察局前往安全屋避难。
已知浣熊市是个nm的区域，每块格子的类型有以下几种： ：表示第0秒时该地点有病毒，且每过1秒病毒就会往上/下/左/右四个方向扩散一格，被病毒新侵占的格子又会按照此规则继续扩散。
S：表示警察局，也就是PIPI一开始所在的地方。
T：表示安全屋，任何病毒都不能扩散到安全屋，这也是PIPI要到达的地方。
#：表示该地点已被摧毁，病毒无法扩散到该地点，同时PIPI也无法移动到该地点。
.： 表示空地。
以上类型中，如无特别说明的，均能被病毒扩散到。
PIPI每秒可以往上/下/左/右四个方向移动一格，由于PIPI希望能在警察局搜集到足够多的物资，所以他想保证自己在逃亡之旅上不会被病毒感染的情况下，尽可能的在警察局待得久。
请问PIPI在警察局最多能待多少秒？

emmm 首先根据病毒，计算所有点被感染的时刻，将所有点压入队列跑 bfs (不要每个点都跑一次！！)

T到哭… 然后二分的时候注意边界（可能you时候不太需要QAQ）！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
int n,m,ans,ex,ey,fx,fy,te[MAX][MAX],aw[4][2]={-1,0,0,1,1,0,0,-1};
char a[MAX][MAX]; 
int vis[MAX][MAX];
bool judge(int x,int y){
	if(x<1||x>n||y<1||y>m) return false;
	return true;
}
struct node{
	int x,y,d;
	node(int _x,int _y,int _d){
		x=_x;y=_y;d=_d;
	}
};
queue<node>virus;
void bfs(){
	while(!virus.empty()){
		node t=virus.front();
		virus.pop();
		te[t.x][t.y]=min(te[t.x][t.y],t.d);
		fi(i,0,4){
			int tx=t.x + aw[i][0];
			int ty=t.y + aw[i][1];
			if(judge(tx,ty) && !vis[tx][ty] && a[tx][ty]!='#' && a[tx][ty]!='T'){
				if(te[t.x][t.y] + 1 < te[tx][ty]) {
					virus.push(node(tx,ty,te[t.x][t.y]+1));
					vis[tx][ty] =1;
				}
			}
		}
	}
}
//start on d time
bool isok(int d){
	queue<node> q;
	q.push(node(fx,fy,d));
	vis[fx][fy]=d;
	while(!q.empty()){
		node t=q.front();
		q.pop();
		if(t.x==ex&&t.y==ey) return true;
		fi(i,0,4){
			int tx=t.x + aw[i][0];
			int ty=t.y + aw[i][1];
			if(judge(tx,ty) && vis[tx][ty]!=d && a[tx][ty]!='#'&&t.d+1<te[tx][ty]){
				vis[tx][ty]=d;
				q.push(node(tx,ty,t.d+1));
			}
		}
	}
	return false;
}
int main(){
	freopen("in","r",stdin);
	sf(n);sf(m);
	fi(i,1,n+1){
		scanf("%s",a[i]+1); 
	}
	mem(te,0x3f);//time
	fi(i,1,n+1)
		fi(j,1,m+1){
			if(a[i][j]=='*'){
				virus.push(node(i,j,1));
				vis[i][j]=1;
			}else if(a[i][j]=='T'){
				ex=i;ey=j;
			}else if(a[i][j]=='S'){
				fx=i;fy=j;
			}
		}
	bfs();
	mem(vis,-1);
	int l=1,r=te[fx][fy]-1;//!!!! te[fx][fy]时刻走已经晚了！ 
	while(l<=r){
		int m=(l+r)/2;
		if(isok(m)){
			ans = m;
			l = m+1;
		}else r=m-1;
	}
	pf(ans-1);
	return 0;
}