Description：

当阿尔萨斯到达斯坦索姆的同时，光明使者乌瑟尔也及时赶来。但这时众人骇然发现一切都已经太晚了——被瘟疫感染的谷物已经发放到市民手中!

这些无辜的市民必将会感染瘟疫而成为天灾军团的部队。于是阿尔萨斯命令乌瑟尔和白银之手骑士团屠杀市民。当乌瑟尔拒绝执行这个命令时，阿尔萨斯竟然宣判德高望重的光明使者叛国。心灰意冷的乌瑟尔和他麾下的圣骑士愤然离城。而吉安娜也极其失望地离开。在最绝望无助的时候，没有人愿意支持年轻王子的抉择，留给他的只剩下无尽的痛苦。尽管众叛亲离，阿尔萨斯还是将他的计划付诸实施。他命令士兵将感染瘟疫的无辜市民屠戮殆尽，并把城内所有的建筑烧得一干二净!但是同时，恐惧魔王梅尔甘尼斯也正在将市民们转化为不死族。

给出斯坦索姆的地图和阿尔萨斯与梅尔甘尼斯的位置，每分钟阿尔萨斯和梅尔甘尼斯会在部队所在的地方屠杀市民,当房子烧毁后，阿尔萨斯会派他的军队向4个房屋未烧毁的方向(上下左右)移动。

阿尔萨斯想知道是他还是梅尔甘尼斯杀的比较快，于是要求你这位御用编程师将k分钟后的情况给他。

注意：如果阿尔萨斯和梅尔甘尼斯相遇，则阿尔萨斯会击退梅尔甘尼斯再烧毁房屋。

Input：

输入文件名为massacre.in。

输入的第一行包含两个数n、m和k，表示城市的长、宽和阿尔萨斯想知道情况的时间。

接下来n行，每行m个字符（中间无空格），‘A’表示阿尔萨斯，‘M’表示梅尔甘尼斯，‘#’表示墙，‘.’表示房子。

Output：

输出文件名为massacre.out。

输出k分钟后的情况，被阿尔萨斯消灭的房子用‘a’表示，梅尔甘尼斯的用‘m’表示。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n , m , k , nx , ny , mx , my;
int dx[4] = {0 , 1 , -1 , 0};
int dy[4] = {1 , 0 , 0 , -1};
char mapp[505][505];
struct fxy{
    int x;
    int y;
    int t;
};
queue<fxy>qm;
queue<fxy>qn;
 
void bfs()
{
    fxy a , b;
    a.x = nx;
    a.y = ny;
    a.t = 0;
    b.x = mx;
    b.y = my;
    b.t = 0;
    qn.push(a);
    qm.push(b);
    //cout << k + 1 << endl;
    while(!qn.empty() || !qm.empty()){
        if(!qn.empty()){
        	int x1 = qn.front().x;
        	int y1 = qn.front().y;
        	int t1 = qn.front().t;
        	for(int i = 0;i < 4;i ++){
	            int xx1 = x1 + dx[i];
	            int yy1 = y1 + dy[i];
	            if(xx1 >= 1 && xx1 <= n && yy1 >= 1 && yy1 <= m && mapp[xx1][yy1] != '#' && t1 + 1 <= k && mapp[xx1][yy1] != 'A' && mapp[xx1][yy1] != 'a' && mapp[xx1][yy1] != 'M'){
	                fxy step;
	                step.x = xx1;
	                step.y = yy1;
	                step.t = t1 + 1;
	                //cout << step.t << endl;
	                //cout << step.t << endl;
	                qn.push(step);
	                mapp[xx1][yy1] = 'a';
	            }
	        }
	        qn.pop();
		}
		if(!qm.empty()){
			int x2 = qm.front().x;
	        int y2 = qm.front().y;
	        int t2 = qm.front().t;
			for(int i = 0;i < 4;i ++){
	            int xx2 = x2 + dx[i];
	            int yy2 = y2 + dy[i];
	            if(xx2 >= 1 && xx2 <= n && yy2 >= 1 && yy2 <= m && mapp[xx2][yy2] == '.' && t2 + 1 <= k){
	                fxy step;
	                step.x = xx2;
	                step.y = yy2;
	                step.t = t2 + 1;
	                //cout << step.t << endl;
	                //cout << step.t << endl;
	                qm.push(step);
	                mapp[xx2][yy2] = 'm';
	            }
	        }
	        qm.pop();
		}
        //cout << t1 << endl;
    }
    return;
}
 
signed main()
{
    //freopen("massacre.in" , "r" , stdin);
    //freopen("massacre.out" , "w" , stdout);
    cin >> n >> m >> k;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++){
            cin >> mapp[i][j];
            if(mapp[i][j] == 'A'){
                nx = i;
                ny = j;
            }
            if(mapp[i][j] == 'M'){
                mx = i;
                my = j;
            }
        }
    bfs();
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            if(i == nx && j == ny)
                cout << 'A';
            else
                cout << mapp[i][j];
        }
        cout << endl;
    }
    return 0;
}
 

只有80分（QAQ）

求dalao帮忙调 orz