http://tjuacm.chaosheng.top/problem.php?id=1270
http://acm.hdu.edu.cn/showproblem.php?pid=2612
第一反应,对于每个KFC,分别求F和M要花的时间,加起来,每次记录最小的。
能通过样例,但WA。然后看了别的的思路,发现我这样每次都要从头算,一次bfs先把F和M 分别到所有KFC 的时间算出来,之后对每个KFC只要把相应的值加起来就行。所以直接按新思路写了,没有调下面这种方法,不知道哪里不足。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
typedef pair<int, int> P;

const int INF = 1e8;
const int N = 210;

int n, m;
int beginx1, beginy1, beginx2, beginy2;
char matrix[N][N];
bool vis[N][N];
int row[4] = {1, 0, -1, 0};
int col[4] = {0, 1, 0, -1}; 

struct pos{
    int x, y;
    int cost;
};

int bfs(int beginx, int beginy, int endx, int endy){
    queue<pos> q;
    pos f;
    f.x = beginx;
    f.y = beginy;
    f.cost = 0;
    q.push(f);
    vis[f.x][f.y] = true;

    while(q.size()){
        f = q.front();
        q.pop();

        //满足条件
        if(f.x == endx && f.y == endy){
            //printf("!cost = %d\n", f.cost);
            return f.cost;
        }

        for(int i = 0; i < 4; i++){
            pos v = f;
            v.x = f.x + row[i];
            v.y = f.y + col[i];
            if(v.x >= 0 && v.x < n && v.y >= 0 && v.y < n && !vis[v.x][v.y] && matrix[v.x][v.y] != '#'){
                vis[v.x][v.y] = true;
                v.cost += 11;
                //printf("cost = %d\n", v.cost);
                q.push(v);
            }
        }        
    }
}

int main(){
    while(cin >> n >> m){
        vector<P> des;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                cin >> matrix[i][j];
                if(matrix[i][j] == 'Y'){
                    beginx1 = i;
                    beginy1 = j;
                }

                if(matrix[i][j] == 'M'){
                    beginx2 = i;
                    beginy2 = j;
                }

                if(matrix[i][j] == '@'){
                    des.push_back(P(i, j));
                }
            }
        }
        int ans = INF;
        for(auto d : des){
            memset(vis, false, sizeof(vis));
            //printf("dx = %d, dy = %d\n", d.first, d.second);
            int sum1 = bfs(beginx1, beginy1, d.first, d.second);
            memset(vis, false, sizeof(vis));
            int sum2 = bfs(beginx2, beginy2, d.first, d.second);
            //printf("sum1 = %d, sum2 = %d\n", sum1, sum2);
            ans = min(ans, sum1 + sum2);
        }
        printf("%d\n", ans);
    }
    return 0;
}

真的要注意细节哇!!!!!!!!!!!
WA了好多次才发现,一开始输入matrix的j应该是<m,但是写成了n!!!!所以一晚上怎么改bfs都不对,绝了QAQ
然后把第一种我原来想的也就是上面的代码改过来,不再是WA,但会超时。所以还是要用下面的写法。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int n, m;
int yx,yy,mx,my;//Y的坐标,M的坐标
char map[202][202];
int a[202][202];//保存第一个人Y到各个节点(坐标)的最小步数,有的节点不用访问,下面有说明
int b[202][202];//保存第二个人M 
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0}; 

struct pos{
    int x, y;
};

void bfs(int x, int y, int num[202][202]){
    queue<pos> q;
    pos f, v;
    f.x = x;
    f.y = y;
    num[f.x][f.y] = 0;
    q.push(f);

    while(!q.empty()){
        f = q.front();
        q.pop();
        for(int i = 0; i < 4; i++){
            v.x = f.x + dx[i];
            v.y = f.y + dy[i];
            if(v.x >= 0 && v.x < n && v.y >= 0 && v.y < m && num[v.x][v.y] == 0 && map[v.x][v.y] != '#') {
                num[v.x][v.y] = num[f.x][f.y] + 1;
                q.push(v);
            }
        }        
    }
}

int main(){
    while(cin >> n >> m){
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cin >> map[i][j];
                if(map[i][j] == 'Y'){
                    yx = i;
                    yy = j;
                }

                else if(map[i][j] == 'M'){
                    mx = i;
                    my = j;
                }
            }
        }
        bfs(yx,yy,a);
        bfs(mx,my,b);

        int ans = 1000000;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++){
            if(map[i][j] == '@' && b[i][j] != 0){
                ans = min(ans, a[i][j] + b[i][j]);//某个KFC地点两者到达的总步数之和,取最小值。
            }
        }
        cout << ans * 11 << endl;
    }
    return 0;
}