深搜题，注意的是剪枝——剩下的格子不够了就return。 单开两个一位数组记录挺方便，没有习惯性map。
#include <cstdio> #include <iostream> #include <utility> #include <vector> using namespace std; typedef pair<int, int> P; #define rep(i, ll, nn) for(int i = (ll); i <= (nn); i++) #define N 10 char maze[N][N]; int n, k, num; char c; int cnt; bool ux[N], uy[N]; bool ok(int x, int y) { return (!ux[x] && !uy[y] && maze[x][y] == '#'); } void dfs(int x, int left) { if(left == 0){ cnt++; return; } if(n - x < left || x == n + 1) return; rep(j, 1, n){ if(ok(x + 1, j)){ ux[x + 1] = uy[j] = true; dfs(x + 1, left - 1); ux[x + 1] = uy[j] = false; } } dfs(x + 1, left); } int main() { while(scanf("%d%d", &n, &k) != EOF && n > 0){ rep(i, 1, n) rep(j, 1, n) cin >> maze[i][j]; cnt = 0; dfs(0, k); printf("%d\n", cnt); } return 0; }三维的宽搜，其他都是一样的裸的板子。
#include <queue> #include <cstdio> #include <iostream> #include <utility> #include <cstring> #include <vector> using namespace std; typedef pair<int, int> P; #define rep(i, ll, nn) for(int i = (ll); i <= (nn); i++) #define N 32 struct node{ int x, y, z; node(int a = 1, int b = 1, int c = 1):x(a), y(b), z(c){} }; int l, r, c; char maze[N][N][N]; int sx, sy, sz, ex, ey, ez; int ans; queue<node> que; bool used[N][N][N]; int dis[N][N][N]; int dx[] = {0, 0, 1, 0, 0, -1}; int dy[] = {0, 1, 0, 0, -1, 0}; int dz[] = {1, 0, 0, -1, 0, 0}; int bfs() { memset(used, 0, sizeof used); memset(dis, 0, sizeof dis); while(!que.empty()) que.pop(); int x, xx, y, yy, z, zz; node tmp; dis[sx][sy][sz] = 0; used[sx][sy][sz] = true; que.push(node(sx, sy, sz)); while(!que.empty()){ tmp = que.front();que.pop(); x = tmp.x; y = tmp.y; z = tmp.z; if(x == ex && y == ey && z == ez){ return dis[x][y][z]; } rep(i, 0, 5){ xx = x + dx[i];yy = y + dy[i];zz = z + dz[i]; if(xx < 1 || yy < 1 || zz < 1) continue; if(xx > l || yy > r || zz > c) continue; if(used[xx][yy][zz] || maze[xx][yy][zz] == '#') continue; used[xx][yy][zz] = true; dis[xx][yy][zz] = dis[x][y][z] + 1; que.push(node(xx, yy, zz)); } } return -1; } int main() { freopen("date.txt", "r", stdin); char ch; while(scanf("%d%d%d", &l, &r, &c) != EOF && l){ rep(i, 1, l) rep(j, 1, r) rep(k, 1, c){ cin >> ch; if(ch == 'S'){ sx = i; sy = j; sz = k; } else if(ch == 'E'){ ex = i; ey = j; ez = k; } maze[i][j][k] = ch; } //rep(i, 1, l) rep(j, 1, r) rep(k, 1, c) { // cout << maze[i][j][k]; // if(k == c) cout << '\n'; //} ans = bfs(); if(ans == -1) printf("Trapped!\n"); else printf("Escaped in %d minute(s).\n", ans); } return 0; }一维宽搜
#include <queue> #include <cstdio> #include <iostream> #include <utility> #include <cstring> #include <vector> using namespace std; typedef pair<int, int> P; #define rep(i, ll, nn) for(int i = (ll); i <= (nn); i++) #define N 100005 int n, k; int sx, ex; int ans; queue<int> que; bool used[N]; int dis[N]; int bfs() { if(sx == ex) return 0; memset(used, 0, sizeof used); memset(dis, 0, sizeof dis); while(!que.empty()) que.pop(); int x, xx; dis[sx] = 0; dis[ex] = 1000000000; used[sx] = true; que.push(sx); while(!que.empty()){ x = que.front();que.pop(); rep(i, 0, 2){ if(i == 0) xx = x * 2; if(i == 1) xx = x + 1; if(i == 2) xx = x - 1; if(xx < 0 || used[xx]) continue; if(xx >= ex){ dis[ex] = min(dis[ex], xx - ex + dis[x] + 1); continue; } used[xx] = true; dis[xx] = dis[x] + 1; que.push(xx); } } return dis[ex]; } int main() { //freopen("date.txt", "r", stdin); while(scanf("%d%d", &n, &k) != EOF){ sx = n;ex = k; printf("%d\n", bfs()); } return 0; }这题还挺难好像，用二进制数来状态压缩显得很有逼格~~~ 解决思想是先枚举第一行的翻法，然后第一行确定了下一行身不由己的要承担起把上一行变换成全白的责任，递推下去看最后一行是不是全白就ok了。 这题既然放在搜索里大概能用搜索写？以后试试。
#include <queue> #include <cstdio> #include <iostream> #include <utility> #include <cstring> #include <vector> using namespace std; typedef pair<int, int> P; #define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++) #define N 17 const int INF = 0x3f3f3f3f; typedef long long ll; int m, k, n, num; int maze[N][N], ans[N][N], out[N][N]; int dx[] = {1, -1, 0, 0, 0}; int dy[] = {0, 0, 1, -1, 0}; int get(int x, int y) { int cnt = maze[x][y]; rep(i, 0, 4)cnt += ans[x + dx[i]][y + dy[i]]; return cnt & 1; } int solve() { rep(i, 2, m) rep(j, 1, k) ans[i][j] = get(i - 1, j); rep(j, 1, k) if(get(m, j)) return -1; int cnt = 0; rep(i, 1, m) rep(j, 1, k) cnt += ans[i][j]; return cnt; } int main() { //freopen("date.txt", "r", stdin); scanf("%d%d", &m, &k); rep(i, 1, m) rep(j, 1, k) scanf("%d", &maze[i][j]); n = 1 << k; num = INF; rep(i, 0, n - 1){ memset(ans, 0, sizeof ans); rep(j, 0, k - 1) ans[1][k - j] = i >> j & 1; int cnt = solve(); if(cnt >= 0 && num > cnt){ num = cnt; memcpy(out, ans, sizeof ans); } } if(num == INF) printf("IMPOSSIBLE\n"); else { rep(i, 1, m) rep(j, 1, k) printf("%d%c", out[i][j], j == k?'\n':' '); } return 0; }输入一个数找到它的只有01的倍数。乍一看搜索量极其巨大，然则它的倍数是无限的然而01组成的数是少得多的，所以直接搜01组成的数判断是否是n的倍数就ok。
#include <queue> #include <cstdio> #include <iostream> #include <utility> #include <cstring> #include <vector> using namespace std; typedef pair<int, int> P; #define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++) #define N 17 const int INF = 0x3f3f3f3f; typedef long long ll; queue<ll> que; ll solve(int n) { while(!que.empty()) que.pop(); que.push(1); while(true){ ll tmp = que.front();que.pop(); if(tmp % n == 0) return tmp; que.push(tmp * 10); que.push(tmp * 10 + 1); } } int main() { int n; while(cin >> n && n){ cout << solve(n) << endl; } return 0; }昂模拟题，map，string大法好。
#include <cstdio> #include <cstring> #include <utility> #include <iostream> #include <map> #include <string> using namespace std; typedef pair<string, string> P; #define N 101 #define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++) string s1, s2, s12, t1, t2, t12; int t, c, ans; map<string, bool> mp; int main() { scanf("%d", &t); rep(Case, 1, t){ mp.clear(); scanf("%d", &c); cin >> s1 >> s2 >> s12; ans = 0; t1 = s1;t2 = s2; while(true){//printf("%s %s\n", t1, t2); ++ans; t12.clear(); rep(i, 0, c - 1){ t12 += t2[i];t12 += t1[i]; } //cout << t1 <<' ' << t2 << endl; if(t12 == s12){ printf("%d %d\n", Case, ans);break; } else if(mp[t12]){ printf("%d -1\n", Case);break; } t1.clear();t2.clear(); rep(i, 0, c - 1) t1 += t12[i]; rep(i, c, c * 2 - 1) t2 += t12[i]; mp[t12] = true; } } return 0; }记忆路径的宽搜
#include <cstdio> #include <cstring> #include <utility> #include <iostream> #include <map> #include <string> #include <queue> using namespace std; typedef pair<int, int> P; #define N 101 #define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++) int a, b, c; string op[6] = {"FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"}; struct opt{ int d, pa, x, y, z; opt(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0):d(a),pa(b),x(c),y(d),z(e){} }path[N * N]; bool vis[N][N]; int bfs() { int l = 0; path[l] = opt(0, -1, 0, 0); vis[0][0] = true; queue<opt> que; que.push(opt(1, l - 1, a, 0, 0)); que.push(opt(1, l - 1, 0, b, 1)); while(!que.empty()){ path[l] = que.front();que.pop(); opt & q = path[l]; if(q.x == c || q.y == c){ return l; } if(q.x != a && !vis[a][q.y]){ vis[a][q.y] = true; que.push(opt(q.d + 1, l, a, q.y, 0)); } if(q.y != b && !vis[q.x][b]){ vis[q.x][b] = true; que.push(opt(q.d + 1, l, q.x, b, 1)); } if(q.x != 0 && !vis[0][q.y]){ vis[0][q.y] = true; que.push(opt(q.d + 1, l, 0, q.y, 2)); } if(q.y != 0 && !vis[q.x][0]){ vis[q.x][0] = true; que.push(opt(q.d + 1, l, q.x, 0, 3)); } int k = min(q.x, b - q.y); if(k > 0 && !vis[q.x - k][q.y + k]){ vis[q.x - k][q.y + k] = true; que.push(opt(q.d + 1, l, q.x - k, q.y + k, 4)); } k = min(a - q.x, q.y); if(k > 0 && !vis[q.x + k][q.y - k]){ vis[q.x + k][q.y - k] = true; que.push(opt(q.d + 1, l, q.x + k, q.y - k, 5)); } l++; } return -1; } int main() { cin >> a >> b >> c; int t = bfs(); if(t == -1) printf("impossible\n"); else{ cout << path[t].d << endl; int ans[N * N], l = 0; ans[l++] = path[t].z; while(path[t].pa != -1){ t = path[t].pa; ans[l++] = path[t].z; // cout << path[t].x << ' ' << path[t].y << endl; } for(int i = l - 2; i >= 0; i--) cout << op[ans[i]] << endl; } return 0; }老老实实宽搜
#include <queue> #include <cstdio> #include <iostream> #include <utility> #include <cstring> #include <vector> #include <map> using namespace std; typedef pair<int, int> P; #define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++) #define N 17 const int INF = 0x3f3f3f3f; typedef long long ll; bool pri[10000]; queue<P> que; map<P, int> ans; bool vis[10000]; int change(int s, int d, int to) { if(d == 1) return (s / 10) * 10 + to; else if(d == 2) return (s / 100) * 100 + to * 10 + s % 10; else if(d == 3) return (s / 1000) * 1000 + to * 100 + s % 100; else return to * 1000 + s % 1000; } int solve(int s, int e) { while(!que.empty()) que.pop(); que.push(P(s, 0)); P h; int t; vis[s] = true; while(!que.empty()){ h = que.front();que.pop(); if(h.first == e) return h.second; if(h.second > 10) continue; rep(i, 1, 4) rep(j, 0, 9) { t = change(h.first, i, j); if(t != h.first && pri[t] && t > 1000 && !vis[t]){ vis[t] = true; que.push(P(t, h.second + 1)); } } } } int main() { int s, e, t; memset(pri, true, sizeof pri); rep(i, 2, 5000) if(pri[i]){ for(int j = i * 2; j < 10000; j += i) pri[j] = false; } //cout << pri[19] << endl; cin >> t; while(t--){ cin >> s >> e; memset(vis, 0, sizeof vis); int ans = solve(s, e); if(ans == -1) printf("Impossible\n"); else printf("%d\n", ans); } return 0; }为了特殊的游戏要有合适的场地，要把草少了，要烧得快。枚举任意两个点来宽搜。
#include <cstdio> #include <cstring> #include <utility> #include <iostream> #include <map> #include <string> #include <queue> using namespace std; typedef pair<int, int> P; #define N 11 #define f first #define s second #define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++) char maze[N][N]; int n, m; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; int d[N][N]; bool vis[N][N]; int bfs(int x1, int y1, int x2, int y2) { memset(d, 0, sizeof d); memset(vis, false, sizeof vis); queue<P> que; que.push(P(x1, y1)); d[x1][y1] = 0; vis[x1][y1] = true; if(maze[x2][y2] == '#' && !vis[x2][y2]){ que.push(P(x2, y2)); d[x2][y2] = 0; vis[x2][y2] = true; } while(!que.empty()){ P h = que.front(); que.pop(); for(int i = 0; i < 4; i++){ int x = h.f + dx[i], y = h.s + dy[i]; if(x < 0 || x >= n || y < 0 || y >= m) continue; if(maze[x][y] == '.' || vis[x][y]) continue; vis[x][y] = true; que.push(P(x, y)); d[x][y] = d[h.f][h.s] + 1; } } rep(i, 0, n - 1) rep(j, 0, m - 1) if(maze[i][j] == '#' && !vis[i][j]) return -1; int cnt = -1; rep(i, 0, n - 1) rep(j, 0, m - 1) cnt = max(cnt, d[i][j]); return cnt; } int main() { int t; scanf("%d", &t); rep(Case, 1, t){ scanf("%d%d", &n, &m); rep(i, 0, n - 1) scanf("%s", maze[i]); int ans = -1; rep(i, 0, n - 1) rep(j, 0, m - 1) rep(k, 0, n - 1) rep(l, 0, m - 1){ if(maze[i][j] == '#' && maze[k][l] == '#'){ int t = bfs(i, j, k, l); if(t >= 0 && (ans == -1 || ans > t)) ans = t;//cout << i << ' ' << j << ' ' << k <<' ' << l << endl; } } printf("Case %d: %d\n", Case, ans); } return 0; }分两次搜，第一次预处理出火烧的时间，第二次搜人。 mmp我把d初始化成-1最后比较的时候忘了特判。初始化INF就不会这样了。
#include <cstdio> #include <cstring> #include <utility> #include <iostream> #include <map> #include <string> #include <queue> using namespace std; typedef pair<int, int> P; #define N 1001 #define fi first #define se second #define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++) int n, m, ans; char maze[N][N]; int d[N][N], flee[N][N]; bool vis[N][N]; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; queue<P> que; void bfs(int tpe) { memset(vis, false, sizeof vis); while(!que.empty()) que.pop(); if(tpe == 1){ memset(d, -1, sizeof d); rep(i, 0, n - 1) rep(j, 0, m - 1) if(maze[i][j] == 'F') { que.push(P(i, j)); d[i][j] = 0; vis[i][j] = true; } } else{ ans = -1; memset(flee, 0, sizeof flee); rep(i, 0, n - 1) rep(j, 0, m - 1) if(maze[i][j] == 'J'){ que.push(P(i, j)); flee[i][j] = 0; vis[i][j] = true; break; } } while(!que.empty()){ P h = que.front(); que.pop(); if(tpe == 2) if(h.fi == 0 || h.fi == n - 1 || h.se == 0 || h.se == m - 1){//printf("x %d y %d\n", h.fi, h.se); ans = flee[h.fi][h.se] + 1; break; } rep(i, 0, 3){ int x = h.fi + dx[i], y = h.se + dy[i]; if(x < 0 || x >= n || y < 0 || y >= m) continue; if(maze[x][y] == '#' || vis[x][y]) continue; if(tpe == 2 && d[x][y] != -1 && flee[h.fi][h.se] + 1 >= d[x][y]) continue; if(tpe == 1) d[x][y] = d[h.fi][h.se] + 1; else flee[x][y] = flee[h.fi][h.se] + 1; vis[x][y] = true; que.push(P(x, y)); } } } int main() { // freopen("data.txt", "r", stdin); int t; scanf("%d", &t); while(t--){ scanf("%d%d", &n, &m); rep(i, 0, n - 1) scanf("%s", maze[i]); bfs(1);//rep(i, 0, n - 1) rep(j, 0, m - 1) printf("%d%c", d[i][j], j == m - 1?'\n':' '); bfs(2); if(ans == -1) printf("IMPOSSIBLE\n"); else printf("%d\n", ans); } return 0; }宽搜记忆路径
#include <string> #include <queue> #include <cstdio> #include <cstring> #include <utility> #include <iostream> #include <map> using namespace std; typedef pair<int, int> P; #define N 5 #define fi first #define se second #define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++) int maze[N][N]; P path[N][N]; int d[N][N]; queue<P> que; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; void bfs() { memset(d, 0x3f, sizeof d); que.push(P(0, 0)); d[0][0] = 0; while(!que.empty()){ P h = que.front(); que.pop(); if(h.fi == 4 && h.se == 4) return; rep(i, 0, 3){ int x = h.fi + dx[i], y = h.se + dy[i]; if(x < 0 || x >= N || y < 0 || y >= N) continue; if(maze[x][y] == 1) continue; if(d[x][y] <= d[h.fi][h.se] + 1) continue; d[x][y] = d[h.fi][h.se] + 1; path[x][y] = h; que.push(P(x, y)); } } } int main() { //freopen("data.txt", "r", stdin); rep(i, 0, 4) rep(j, 0, 4) scanf("%d", &maze[i][j]); bfs(); P ans[N * N]; int l = 0; ans[l++] = P(4, 4); int x = 4, y = 4; while(!(x == 0 && y == 0)){ ans[l++] = path[x][y]; x = ans[l - 1].fi; y = ans[l - 1].se; } for(int i = l - 1; i >= 0; i--) printf("(%d, %d)\n", ans[i].fi, ans[i].se); return 0; }深搜求连通度。我第一道深搜题就是这个题型，亲切。
#include <string> #include <queue> #include <cstdio> #include <cstring> #include <utility> #include <iostream> #include <map> using namespace std; typedef pair<int, int> P; #define N 101 #define fi first #define se second #define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++) char maze[N][N]; int n, m; int cnt; int dx[] = {0, 0, 1, -1, 1, 1, -1, -1}; int dy[] = {1, -1, 0, 0, 1, -1, 1, -1}; void dfs(int x, int y) { maze[x][y] = '*'; rep(i, 0, 7) { int xx = x + dx[i], yy = y + dy[i]; if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue; if(maze[xx][yy] == '*') continue; dfs(xx, yy); } } int main() { //freopen("data.txt", "r", stdin); while(~scanf("%d%d", &n, &m) && n){ rep(i, 0, n - 1) scanf("%s", maze[i]); cnt = 0; rep(i, 0, n - 1) rep(j, 0, m - 1) if(maze[i][j] == '@'){ dfs(i, j); cnt++; } printf("%d\n", cnt); } return 0; }重复代码的复制要谨慎。。。
#include <string> #include <queue> #include <cstdio> #include <cstring> #include <utility> #include <iostream> #include <map> using namespace std; //typedef pair<int, int> P; #define N 101 #define fi first #define se second #define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++) struct P{ int a, b, c; P (int x=0, int y=0, int z=0):a(x), b(y), c(z){} bool judge(){ return (a == b && c == 0) || (b == c && a == 0) || (c == a && b == 0); } bool operator < (P t) const{ if(a == t.a) { if(b == t.b) return c < t.c; return b < t.b; } return a < t.a; } }; map<P, int> d; queue<P> que; int bfs(int n, int m, int z) { d.clear(); while(!que.empty()) que.pop(); int dif; que.push(P(n, 0, 0)); d[P(n, 0, 0)] = 0; while(!que.empty()){ P h = que.front(); que.pop(); if(h.judge()) return d[h]; //if(n == 4)printf("%d %d %d\n", h.a, h.b, h.c); if(h.a != 0 && h.b < m){ dif = min(h.a, m - h.b); P tmp = P(h.a - dif, h.b + dif, h.c); if(!d[tmp]) d[tmp] = d[h] + 1, que.push(tmp); } if(h.a != 0 && h.c < z){ dif = min(h.a, z - h.c); P tmp = P(h.a - dif, h.b, h.c + dif); if(!d[tmp]) d[tmp] = d[h] + 1, que.push(tmp); } if(h.b != 0 && h.c < z){ dif = min(h.b, z - h.c); P tmp = P(h.a, h.b - dif, h.c + dif); if(!d[tmp]) d[tmp] = d[h] + 1, que.push(tmp); } if(h.b != 0 && h.a < n){ dif = min(n - h.a, h.b); P tmp = P(h.a + dif, h.b - dif, h.c); if(!d[tmp]) d[tmp] = d[h] + 1, que.push(tmp); } if(h.c != 0 && h.a < n){ dif = min(h.c, n - h.a); P tmp = P(h.a + dif, h.b, h.c - dif); if(!d[tmp]) d[tmp] = d[h] + 1, que.push(tmp); } if(h.c != 0 && h.b < m){ dif = min(h.c, m - h.b); P tmp = P(h.a, h.b + dif, h.c - dif); if(!d[tmp]) d[tmp] = d[h] + 1, que.push(tmp); } } return -1; } int main() { //freopen("data.txt", "r", stdin); int a, b, c, ans; while(~scanf("%d%d%d", &a, &b, &c) && a + b + c){ if((ans = bfs(a, b, c)) == -1) puts("NO"); else printf("%d\n", ans); } return 0; }又是搜两次。
#include <string> #include <queue> #include <cstdio> #include <cstring> #include <utility> #include <iostream> #include <map> using namespace std; typedef pair<int, int> P; #define N 201 #define fi first #define se second #define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++) char maze[N][N]; P Y, M; map<P, bool> mp; int d1[N][N], d2[N][N]; bool vis[N][N]; queue<P> que; int n, m; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; int bfs() { while(!que.empty()) que.pop(); memset(vis, false, sizeof vis); memset(d1, 0x3f, sizeof d1); que.push(Y); d1[Y.fi][Y.se] = 0; int cnt = 0; vis[Y.fi][Y.se] = true; while(!que.empty()){ P h = que.front(); que.pop(); if(mp[h]) cnt++; if(cnt == mp.size()) break; rep(i, 0, 3){ int x = h.fi + dx[i], y = h.se + dy[i]; if(x < 0 || x >= n || y < 0 || y >= m) continue; if(vis[x][y] || maze[x][y] == '#') continue; d1[x][y] = d1[h.fi][h.se] + 1; vis[x][y] = true; que.push(P(x, y)); } } while(!que.empty()) que.pop(); memset(vis, false, sizeof vis); memset(d2, 0x3f, sizeof d2); que.push(M); d2[M.fi][M.se] = 0; cnt = 0; vis[M.fi][M.se] = true; while(!que.empty()){ P h = que.front(); que.pop(); if(mp[h]) cnt++; if(cnt == mp.size()) break; rep(i, 0, 3){ int x = h.fi + dx[i], y = h.se + dy[i]; if(x < 0 || x >= n || y < 0 || y >= m) continue; if(vis[x][y] || maze[x][y] == '#') continue; d2[x][y] = d2[h.fi][h.se] + 1; vis[x][y] = true; que.push(P(x, y)); } } map<P, bool>::iterator it; int ans = 9999999; for(it = mp.begin(); it != mp.end(); it++){ if(!it->se) continue; int x = it->fi.fi, y = it->fi.se; ans = min(d1[x][y] + d2[x][y], ans); } //printf("cnt %d\n", cnt); //if(mp[P(0, 3)]) printf("%d %d\n", d1[0][3], d2[0][3]); //if(mp[P(3, 0)]) printf("%d %d %d\n", d1[3][0], d2[3][0], (int)mp.size()); return ans * 11; } int main() { // freopen("data.txt", "r", stdin); while(~scanf("%d%d", &n, &m)){ rep(i, 0, n - 1) scanf("%s", maze[i]); mp.clear(); rep(i, 0, n - 1) rep(j, 0, m - 1) { if(maze[i][j] == 'Y') Y = P(i, j); else if(maze[i][j] == 'M') M = P(i, j); else if(maze[i][j] == '@') mp[P(i, j)] = 1; } printf("%d\n", bfs()); } return 0; }