Description
MCM/ICM is just as interesting as ACM/ICPC.
If you have participated in MCM/ICM 2019, then you will definitely know about the Problem D about the Louvre.
The specific problem are described below:
Qleonardo also participated in this MCM/ICM. To solve this problem, qleonardo thought of using the cellular automaton model to simulate the evacuation process. However, we are now doing ACM instead of MCM/ICM, so we simplified his model.
Specifically, the plane map of the Louvre is first divided into a number of small squares. Then abstract the person into points and put them in these small squares.
This way we can let everyone move in a specific way. Specifically, we can move everyone to the nearest exit to reduce the time spent on evacuation. However, the size of the exit is fixed. We assume that an exit can only go out of one person per unit time, and each person moves at a speed of 1. In addition, we believe that it is more spacious except for the exit. That is to say, there can be multiple people in a small square in the places except for the exit.
When multiple people want to go out from an exit at the same time, these people will rush out to survive. Therefore, the strongest person will first go out from this exit, and the others will stop in their original position.
Your task is to output the time each person flees the Louvre in accordance with the above rules.
You should be aware that people cannot cross obstacles and can only escape from the exit. If a person is at the same distance from the two exits, then the upper exit is preferred. If there is still the same, the left exit is preferred.
Input
The first line consists of three numbers m,n(2<=n,m<=1,000) and p(1<=p<=1,000,000), representing the width and length of the Louvre plane map and the number of initial people.
Next, a matrix of m*n, 0 means that a certain position can go, 1 means an obstacle, and 2 means an exit.
Next there are p lines, three numbers xi,yi (1<=xi<=m,1<=yi<=n) and wi (0<=wi<=2^31-1) for each line,indicating the initial position coordinates of the i-th person and his strength.
Data guarantees that everyone’s strength is different. Data guarantees that everyone's initial position is not an obstacle nor an exit.
Output
Output a line, a total of p numbers, where the i-th number indicates the time when the i-th person escaped from the Louvre.
If someone can't get to the exit, the person's escape time is -1.
Sample Input
3 5 3
20001
00000
01002
3 4 1
1 3 3
2 2 2
Sample Output
1 2 3
Resume
矩阵上包含出口和障碍，寻找最近出口并根据人的力量大小判断出入顺序。
Analysis
首先找到距离每个人的最近出口，然后用优先队列对每个出口的人进行排序。
在找出口时直接暴力BFS，但要注意以下几点：
- 上方出口更优，然后左边出口更优。
- 从每个出口开始BFS，而非为每个人BFS最近出口。（前者(O(N^2))，后者(O(PN^2))）。
- BFS时注意出口优先度。
然后对每个出口的人顺序进行判断。基本思路是：先进行一次按照时间和力量值的排序，然后对每个时间点做一个关于力量值的优先队列。
这样操作是为了如下情况：
三个人到达出口时间分别为1、1、2，力量值分别为3、1、2.
则离开时间分别为1、3、2.
错误思路主要有两种：
- 简单排一次序就直接当作答案，反例如上。
- 直接做一个优先队列，每次更新时间保证某一时间点时所有人都可以按照力量值排序。这样子的时间复杂度会比较大。
Code
//////////////////////////////////////////////////////////////////////
//Target: 2018校赛 A - Escape LouvreⅠ
//@Author: Pisceskkk
//Date: 2019-5-7
//////////////////////////////////////////////////////////////////////
#include<bits/stdc++.h>
#define mp make_pair
#define N 1010
#define M 1000010
#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a<b?a:b)
using namespace std;
typedef pair<int,int> pii;
int n,m,p,gra[N][N],ans[M],tot;
char c;
struct per{ // 出口处保存人的数据
int num,t,w;
per(int num0,int t0,int w0){
num = num0;
t = t0;
w = w0;
}
bool operator <(per b)const{ // 共两次排序 本次为优先队列
return w < b.w;
}
};
bool com(per a,per b){ // 第一次排序
return a.t == b.t ? (a.w > b.w) : (a.t < b.t);
}
vector<per> e[M];
int dis[N][N],vis[N][N]; // 分别记录时间（距离）和出口编号
queue<pii> q;
priority_queue<per> eq; // 出口处的优先队列
const int mox[4] = { 1, 0, 0,-1};
const int moy[4] = { 0, 1,-1, 0};
inline bool check(int x,int y){
return (0 < x && x <= m && 0 < y && y <= n && gra[x][y] != 1);
}
void bfs(){
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(gra[i][j] == 2){
q.push(mp(i,j));
dis[i][j]=0;
vis[i][j] = ++tot;
//printf("|%d %d %d
",i,j,tot);
}
}
}
int x,y,f,d,xx,yy;
while(!q.empty()){
x = q.front().first;
y = q.front().second;
q.pop();
f = vis[x][y];
d = dis[x][y]+1;
for(int i=0;i<4;i++){
xx = x+mox[i];
yy = y+moy[i];
if(!check(xx,yy))continue;
if(dis[xx][yy] > d){
vis[xx][yy] = f;
dis[xx][yy] = d;
q.push(mp(xx,yy));
}
else if(dis[xx][yy] == d){
vis[xx][yy] = Min(f,vis[xx][yy]);
}
}
}
}
int main(){
scanf("%d %d %d",&m,&n,&p);
for(int i=1;i<=m;i++){
getchar();
for(int j=1;j<=n;j++){
c = getchar();
gra[i][j] = c-'0';
}
}
bfs();
int x,y,w;
for(int i=1;i<=p;i++){
ans[i] = -1;
scanf("%d %d %d",&x,&y,&w);
e[vis[x][y]].push_back(per(i,dis[x][y],w));
//printf("!%d %d %d
",x,y,vis[x][y]);
}
int t,len;
//printf("%d
",tot);
for(int i=1;i<=tot;i++){
sort(e[i].begin(),e[i].end(),com);
len = e[i].size();
//for(int j=0;j<len;j++)printf("~%d %d %d
",e[i][j].num,e[i][j].t,e[i][j].w);
while(!eq.empty())eq.pop();
t = 1;
for(int j=0;j<len;j++){
if(e[i][j].t <= t){
eq.push(e[i][j]);
}
else {
if(eq.empty()){
t = e[i][j].t;
eq.push(e[i][j]);
continue;
}
ans[eq.top().num] += t+1;
eq.pop();
t++;
j--;
}
}
while(!eq.empty()){
ans[eq.top().num] += t+1;
eq.pop();
t++;
}
}
for(int i=1;i<=p;i++){
printf("%d ",ans[i]);
}
return 0;
}