题目背景 ｍｚｃ与ｄｊｎ的第二弹。
题目描述 ｍｚｃ家很有钱（开玩笑），他家有ｎ个男家丁（做过上一弹的都知道）。
他把她们召集在了一起，他们决定玩捉迷藏，现在mzc要来寻找他的男家丁，大家一起来帮忙啊！
由于男家丁数目不多，再加上mzc大大的找人【laopo】水平很好，所以一次只需要找一个男家丁。
输入格式 第一行有两个数ｎ, m，表示有 n 行 m 列供男家丁躲藏， 之后 n 行 m 列的矩阵，m 表示mzc，d 表示男家丁，# 表示不能走，. 表示空地。
输出格式 一行，若有解：一个数ｓｕｍ，表示找到男家丁的最短移动次数。 若无解：输出“No Way!”。
输入样例
5 6 .#..#. ....#. d..... #####. m.....输出样例 12
数据范围 3 ≤ n, m ≤ 2000 由于mzc大大十分着急，所以他只能等待1S。
题解 BFS：
#include <iostream> #include <cstring> #include <queue> #define x first #define y second using namespace std; typedef pair<int, int > PII; const int N = 2010; char g[N][N]; int dist[N][N]; int n, m, x1, y1, x2, y2; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; int bfs() { queue<PII> q; q.push(make_pair(x1, y1)); dist[x1][y1] = 0; while(q.size()) { PII t = q.front(); q.pop(); if(t.x == x2 && t.y == y2) return dist[x2][y2]; for (int i = 0; i < 4; i ++) { int a = t.x + dx[i], b = t.y + dy[i]; if(a < 1 || a > n || b < 1 || b > m || dist[a][b] != -1) continue; if(g[a][b] == '#') continue; q.push(make_pair(a, b)); dist[a][b] = dist[t.x][t.y] + 1; } } return -1; } int main() { cin >> n >> m; for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) { cin >> g[i][j]; if(g[i][j] == 'm') x1 = i, y1 = j; if(g[i][j] == 'd') x2 = i, y2 = j; } memset(dist, -1, sizeof dist); if(bfs() == -1) cout << "No Way!" << endl; else cout << dist[x2][y2] << endl; return 0; }