BFS基礎問題杭電2612 Find a way 1252 Hike on a Graph

BFSとDFSの単純比較
DFSはすべてを遍歴するのに適しています.前のブログの2つのDFSの基礎問題のように、最大数歩歩くことができます.すべての連通領域の数は、すべて遍歴してから知る必要があります.
BFSは、例えば最短距離を求め、直接幅を優先して目的地を探索することができ、すべてを遍歴する必要がなく、最短経路を求めることができる.もちろん,BFSはすべて遍歴した後に最終解が得られる問題にも用いることができる.しかし、BFSは、せいぜい数歩歩けるという問題を解くのに適していない.
以下は杭電2612のリンクです.http://acm.hdu.edu.cn/showproblem.php?pid=2612
2人があって、それぞれ都市の异なっている地方で、彼らはKFCで会うことを约束して(都市の中で多くのKFCがあります)、いくつかの道は歩くことができなくて、いくつか歩くことができて、1つのKFCの位置を求めて、彼らの2人の歩く长さのと最も短いです.
分析:これは2人の長さの和を求めるのが最も短くて、だからすべての人に対して、それぞれKFCの最も短い距離まで求める必要があって、それから加算して最も短い和を求めます.この問題はBFSでしか検索できません.KFCを検索するたびに最短距離になるからです.しかし、DFSは最短距離を得ることができません.彼はその目的地を検索したすべての距離を比較し、最短値を取得する必要がありますが、これらのすべての距離は得られません.
コードは次のとおりです.

#include 
#include 
#include 
#include 
#include 
using namespace std;
int m, n;
char a[205][205];//      
int direction[4][2] = { 0, 1, 0, -1, 1, 0, -1, 0 };
int visited[205][205];//          
int dis[205][205][2]; //               ，    
int flag; //                  
struct node{ //                ，             
    int x, y, step;
    node(int x0, int y0, int step0){ x = x0; y = y0; step = step0; }
};
void bfs(int x, int y){
    visited[x][y] = 1;
    queue q;
    q.push(node(x, y, 0));
    while (!q.empty()){
        node u = q.front(); //       ， pop  
        q.pop();
        int nx, ny;
        for (int i = 0; i < 4; i++){
            nx = direction[i][0] + u.x; //   ，   u.x，  x
            ny = direction[i][1] + u.y;
            if (nx < n&&nx >= 0 && ny < m&&ny >= 0 && visited[nx][ny] == 0 && a[nx][ny] != '#'){
                visited[nx][ny] = 1;
                dis[nx][ny][flag] = u.step + 1;  //  ！   step 1
                q.push(node(nx, ny, u.step + 1));
            }

        }
    }
}

int main(){
    //int m, n;  //   ，      ，           m,n，         ，       BFS
    //  ，              ，  main    
    int x1, y1, x2, y2; //           
    while (scanf("%d%d", &n, &m) != EOF){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                cin >> a[i][j];
                if (a[i][j] == 'Y') { x1 = i; y1 = j; }
                if (a[i][j] == 'M') { x2 = i; y2 = j; }
            }
        }
        memset(dis, 0x1f, sizeof(dis));
        memset(visited, 0, sizeof(visited));
        flag = 0;
        bfs(x1, y1);
        memset(visited, 0, sizeof(visited));
        flag = 1;
        bfs(x2, y2);
        //      ，                
        int mins = 0x1f1f1f1f;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (a[i][j] == '@'){
                    mins = min(mins, dis[i][j][0] + dis[i][j][1]);
                }
            }
        }
        cout << mins*11 << endl;
    }
    return 0;
}

杭電1252
原題リンク:http://acm.hdu.edu.cn/showproblem.php?pid=1252 タイトルは少し理解しにくいです:3つの駒があって、それぞれ3人のプレイヤーが制御して、ゲームの目的はすべての駒を同じ位置に達させることです.制約は次のとおりです.