「kuangbin带你飞」专题一 简单搜索

Posted by StandHR on July 25, 2018
View times

传送门

A.POJ1321 棋盘问题

按顺序每行一个个位置开始,每放一个子,将这列标记,继续放下一行,只要能把全部棋子放下ans+1。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;

int n, k, ans, already;
bool vis[8];
string chessBoard[8];

void init() {
    ans = 0;
    already = 0;
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; i++)
        cin >> chessBoard[i];
}

void dfs(int begin) {
    if (already == k) {
        ans++;
        return;
    }

    if (begin == n)
        return;

    for (int i = 0; i < n; i++) {
        if (chessBoard[begin][i] == '#' && vis[i] == false) {
            vis[i] = true;
            already++;
            dfs(begin + 1);
            vis[i] = false;
            already--;
        }
    }
    dfs(begin + 1);
}

int main()
{
    while (scanf("%d%d", &n, &k) != EOF) {
        if (n == -1 && k == -1)
            break;
        init();
        dfs(0);
        printf("%d\n", ans);
    }
    return 0;
}

B.POJ2251 Dungeon Master

多维和二维一样做,只是方向变多。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

const int maxn = 50;
int L, R, C;
char M[maxn][maxn][maxn];

struct node {
    int l, r, c, step;
    node(int a, int b, int c, int d) : l(a), r(b), c(c), step(d) {}
};

int dir[6][3] = { {0, 0, 1}, {0, 1, 0}, {0, 0, -1}, {0, -1, 0}, {-1, 0, 0}, {1, 0, 0}};

bool vis[maxn][maxn][maxn];

void bfs(node Begin) {
    int x;
    queue<node> Q;
    memset(vis, 0, sizeof(vis));
    vis[Begin.l][Begin.r][Begin.c] = true;
    Q.push(Begin);
    while (Q.size()) {
        node now = Q.front();
        Q.pop();
        for (int i = 0; i < 6; i++) {
            node next(now.l + dir[i][0], now.r + dir[i][1], now.c + dir[i][2], now.step + 1);
            if (next.l < 0 || next.l >= L || next.r < 0 || next.r >= R || next.c < 0 || next.c >= C)
                continue;
            if (M[next.l][next.r][next.c] == '#' || vis[next.l][next.r][next.c] == true)
                continue;
            if (M[next.l][next.r][next.c] == 'E') {
                printf("Escaped in %d minute(s).\n", next.step);
                return;
            } else {
                vis[next.l][next.r][next.c] = true;
                Q.push(next);
            }
        }
    }
    printf("Trapped!\n");
}

int main()
{
    while (scanf("%d%d%d", &L, &R, &C) != EOF) {
        if (L == 0)
            break;
        for (int i = 0; i < L; i++) {
            for (int j = 0; j < R; j++) {
                scanf("%s", M[i][j]);
            }
        }
        for (int i = 0; i < L; i++) {
            for (int j = 0; j < R; j++) {
                for (int k = 0; k < C; k++) {
                    if (M[i][j][k] == 'S') {
                        node Begin(i, j, k, 0);
                        bfs(Begin);
                        break;
                    }
                }
            }
        }
    }
    return 0;
}

C.POJ3278 Catch That Cow

一维的搜索,只要扩展时标记这个点以后不走就行。

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

#define maxn 100005

int n, k;
bool vis[maxn];

struct node {
    int place;
    int step;
};

void init() {
    scanf("%d%d", &n, &k);
    memset(vis, 0, sizeof(vis));
}

void bfs() {
    queue<node> Q;
    node x;
    x.place = n;
    x.step = 0;
    vis[x.place] = true;
    Q.push(x);
    while (Q.size()) {
        node now = Q.front();
        Q.pop();

        for (int i = 0; i < 3; i++) {
            node next;
            if(i == 0)
                next.place = now.place - 1;
            else if (i == 1)
                next.place = now.place + 1;
            else
                next.place = now.place * 2;
            next.step = now.step + 1;

            if (next.place >= 0 && next.place <= maxn && vis[next.place] == false) {
                vis[next.place] = true;
                Q.push(next);
                if (next.place == k) {
                    printf("%d\n", next.step);
                    return;
                }
            }
        }
    }
}

int main()
{
    init();
    if (n >= k)
        printf("%d\n", n - k);
    else
        bfs();
    return 0;
}

D.POJ3279 Fliptile

最终要得到全0,第一行翻或不翻的情况共$2^m$,只要确定了第一行的情况如果再想改变第一行只有翻下一行的点,为了保证全0,下一行只能翻上一行这列还为1的点,依次递推下去,所有的点翻或不翻的状态确定。也就是说第一行的状态决定剩下点状态,于是遍历所有第一行的状态,递推出全部点状态,最后只需判断最后一行的状态,如果全为0则搜到一个结果。

注意:最后要输出翻转次数最少的情况,若有多个相同次数的情况输出字典序最小的结果。

有些题解说题目字典序错了,不用管字典序,反着搜就能AC。只是这题数据弱没有筛出他们错误代码,他们没有注意是在翻转次数最少的前提下输出字典序最小。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int maxn = 20;

int m, n, step, ansStep = 1e6;
int a[maxn][maxn], b[maxn][maxn];
int temp[maxn][maxn], ans[maxn][maxn];

//翻转操作,和1异或
void flip(int i, int j) {
    temp[i][j] = 1;
    b[i][j] ^= 1;
    if (i > 0)
        b[i - 1][j] ^= 1;
    if (j > 0)
        b[i][j - 1] ^= 1;
    if (i < m - 1)
        b[i + 1][j] ^= 1;
    if (j < n - 1)
        b[i][j + 1] ^= 1;
}

//输入初始数据
void init() {
    memset(ans, 0, sizeof(ans));
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &a[i][j]);
}

//temp数组归零,b数组初始为a
void init_temp_b() {
    memset(temp, 0, sizeof(temp));
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            b[i][j] = a[i][j];
}

//遍历第一行所有操作,剩下的行操作即可确定
void Do(int k) {
    for (int i = 0; i < n; i++)
        if (k & (1 << i)) {
            flip(0, i);
            step++;
        }

    for (int i = 1; i < m; i++)
        for (int j = 0; j < n; j++)
            if (b[i - 1][j] == 1) {
                flip(i, j);
                step++;
            }
}

//查看是否找到结果
bool check() {
    for (int i = 0; i < n; i++)
        if (b[m - 1][i])
            return false;
    return true;
}


//判断是否更新ans数组,步数更小,或步数相同字典序小
bool cmp() {
    if (step < ansStep)
        return true;
    else if (step > ansStep)
        return false;
    else {
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (ans[i][j] > temp[i][j])
                    return true;
                else if (ans[i][j] < temp[i][j])
                    return false;
        return false;
    }
}

//更改ans数组
void changeAns() {
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            ans[i][j] = temp[i][j];
}

//输出结果
void print() {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n - 1; j++)
            printf("%d ", ans[i][j]);
        printf("%d\n", ans[i][n - 1]);
    }
}

int main()
{
    init();
    bool k = true;
    for (int i = 0; i < (1 << n); i++) {
        step = 0;
        init_temp_b();
        Do(i);
        bool flag = check();
        if (!flag)
            continue;
        else {
            if(cmp()) {
                changeAns();
                ansStep = step;
                k = false;
            }
        }
    }
    if (k)
        printf("IMPOSSIBLE\n");
    else
        print();
    return 0;
}

E.POJ1426 Find The Multiple

数据范围小long long可以存下,如果n再大点就要用大数来做。

#include <cstdio>
#include <queue>
using namespace std;

typedef long long ll;

int n;

void bfs() {
    queue<ll> Q;
    Q.push(1);
    while (Q.size()) {
        ll now = Q.front();
        Q.pop();
        Q.push(now * 10);
        Q.push(now * 10 + 1);
        if(now % n == 0) {
            printf("%lld\n", now);
            return;
        }
    }
}

int main()
{
    while (scanf("%d", &n) != EOF) {
        if (n == 0)
            break;
        bfs();
    }
    return 0;
}

F.POJ3126 Prime Path

先用简单的素数筛打表将素数存下来,广搜的时候在表里查就行。

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

#define maxn 10005

bool vis[maxn];
bool isPrime[maxn];

void init() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i < maxn; i++) {
        if (isPrime[i] == true) {
            for (int  j = i * i; j < maxn; j += i)
                isPrime[j] = false;
        }
    }
}

struct node {
    int x[4];
    int step;
};

int Start, End;

int getNum(int x[4]) {
    int num = 1000 * x[0] + 100 * x[1] + 10 * x[2] + x[3];
    return num;
}

void bfs() {
    queue<node> Q;
    node now;
    vis[Start] = true;
    now.x[0] = Start / 1000;
    now.x[1] = Start % 1000 / 100;
    now.x[2] = Start % 100 / 10;
    now.x[3] = Start % 10;
    now.step = 0;
    Q.push(now);

    while (Q.size()) {
        now = Q.front();
        Q.pop();
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 10; j++) {
                if ((i == 0 && j == 0) || now.x[i] == j)
                    continue;
                node next;
                memcpy(next.x, now.x, sizeof(now.x));
                next.x[i] = j;
                next.step = now.step + 1;
                int nextNum = getNum(next.x);

                if (vis[nextNum] == false && isPrime[nextNum] == true) {
                    vis[nextNum] = true;
                    Q.push(next);
                    if (nextNum == End) {
                        printf("%d\n", next.step);
                        return;
                    }
                }
            }
        }
    }

    printf("Impossible\n");
}

int main()
{
    init();
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &Start, &End);
        memset(vis, 0, sizeof(vis));
        if (Start == End)
            printf("0\n");
        else
            bfs();
    }
    return 0;
}

G.POJ3087 Shuffle’m Up

只有一个操作单方向的搜索,只要记下走过的状态判下重就行。

#include <cstdio>
#include <string>
#include <iostream>
#include <map>
#include <queue>
using namespace std;

string S1, S2, S12;
int C;

struct node {
    string x;
    int step;
};

string shuffle() {
    string x = "";
    for (int i = 0; i < C; i++) {
        x += S2[i];
        x += S1[i];
    }
    return x;
}

void bfs() {
    map<string, bool> vis;
    queue<node> Q;
    node now;
    now.x = shuffle();
    now.step = 1;
    vis[now.x] = true;
    Q.push(now);
    while (Q.size()) {
        now = Q.front();
        Q.pop();
        S1.clear();
        S2.clear();
        for (int i = 0; i < C; i++)
            S1 += now.x[i];
        for (int i = C; i < 2 * C; i++)
            S2 += now.x[i];
        node next;
        next.x = shuffle();
        next.step = now.step + 1;
        if (vis[next.x] == false) {
            vis[next.x] = true;
            Q.push(next);
            if (next.x == S12) {
                printf("%d\n", next.step);
                return;
            }
        }
    }
    printf("-1\n");
}

int main()
{
    int N;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &C);
        cin >> S1 >> S2 >> S12;
        printf("%d ", i);
        bfs();
    }
    return 0;
}

H.POJ3414 Pots

6个方向,分情况讨论。用map或set存下两个杯子有过的状态判重。

#include <cstdio>
#include <string>
#include <queue>
#include <map>
#include <utility>
#include <iostream>
using namespace std;

typedef pair<int, int> PII;

string operate[6] = {"FILL(1)\n", "FILL(2)\n", "DROP(1)\n",
                     "DROP(2)\n", "POUR(1,2)\n", "POUR(2,1)\n"};

int A, B, C;

struct node {
    int A;
    int B;
    int step;
    string path;
};

void bfs() {
    queue<node> Q;
    map<PII, bool> vis;
    node now;
    now.A = 0;
    now.B = 0;
    now.step = 0;
    vis[PII(now.A, now.B)] = true;
    Q.push(now);
    while (Q.size()) {
        now = Q.front();
        Q.pop();

        for (int i = 0; i < 6; i++) {
            node next = now;
            if (i == 0)
                next.A = A;
            else if (i == 1)
                next.B = B;
            else if (i == 2)
                next.A = 0;
            else if (i == 3)
                next.B = 0;
            else if (i == 4) {
                if (next.A <= B - next.B) {
                    next.B += next.A;
                    next.A = 0;
                } else {
                    next.A -= B - next.B;
                    next.B = B;
                }
            } else {
                if (next.B <= A - next.A) {
                    next.A += next.B;
                    next.B = 0;
                } else {
                    next.B -= A - next.A;
                    next.A = A;
                }
            }

            next.step = now.step + 1;
            next.path = now.path + operate[i];

            if (vis[PII(next.A, next.B)] == false) {
                vis[PII(next.A, next.B)] = true;
                Q.push(next);
                if (next.A == C || next.B == C) {
                    printf("%d\n", next.step);
                    cout << next.path;
                    return;
                }
            }
        }
    }
    printf("impossible\n");
}

int main()
{
    scanf("%d%d%d", &A, &B, &C);
    bfs();
    return 0;
}

I.FZU2150 Fire Game

输入后判断#数量,<=2直接输出0,每次取两个#开始bfs,注意不要重复之前的取法,把所有的搜完取最小,所有情况都不能烧完输出-1.

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;

#define INF 0x3f3f3f3f
const int maxn = 20;

char M[maxn][maxn];
bool vis[maxn][maxn];
int dir[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int n, m;
int ans;

struct node {
    int x, y;
    int step;
    node(int a, int b, int c) : x(a), y(b), step(c){}
    node(){}
};

int bfs(node one, node two) {
    memset(vis, 0, sizeof(vis));
    queue<node> Q;
    vis[one.x][one.y] = true;
    vis[two.x][two.y] = true;
    Q.push(one);
    Q.push(two);
    int Max = 0;
    while (Q.size()) {
        node now = Q.front();
        Q.pop();
        for (int i = 0; i < 4; i++) {
            node next;
            next.x = now.x + dir[i][0];
            next.y = now.y + dir[i][1];
            next.step = now.step + 1;
            if (next.x < 0 || next.x >= n || next.y < 0 || next.y >= m)
                continue;
            if (vis[next.x][next.y] == true || M[next.x][next.y] == '.')
                continue;
            Q.push(next);
            vis[next.x][next.y] = true;
        }
        if (now.step > Max)
            Max = now.step;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if(M[i][j] == '.')
                continue;
            if (vis[i][j] == false)
                return -1;
        }
    }
    return Max;
}

void Do() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (M[i][j] == '#') {
                node one(i, j, 0);
                for (int a = i; a < n; a++) {
                    for (int b = 0; b < m; b++) {
                        if (a == i && b <= j) {
                            b = j + 1;
                            continue;
                        }
                        if (M[a][b] == '#') {
                            node two(a, b, 0);
                            int temp = bfs(one, two);
                            if (temp == -1)
                                continue;
                            if (ans > temp)
                                ans = temp;
                        }
                    }
                }
            }
        }
    }
    if (ans == INF)
        printf("-1\n");
    else
        printf("%d\n", ans);
}

int main()
{
    int T, Case = 1;
    scanf("%d", &T);
    while (T--) {
        ans = INF;
        scanf("%d%d", &n, &m);
        int sum = 0;
        for (int i = 0; i < n; i++) {
            scanf("%s", M[i]);
            for (int j = 0; j < m; j++)
                if (M[i][j] == '#')
                    sum++;
        }
        printf("Case %d: ", Case++);
        if (sum <= 2)
            printf("0\n");
        else
            Do();
    }
    return 0;
}

J.UVA11624 Fire!

先用Fire队列BFS,然后看人还能不能走。每个队列交换扩展一层。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

const int maxn = 1005;

char M[maxn][maxn];
bool vis[maxn][maxn];
int dir[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int r, c;

struct node {
    int x, y;
    int step;
    node(int a, int b, int c) : x(a), y(b), step(c){}
    node(){}
};

queue<node> Q[2];

void bfs(node start) {
    if (start.x == 0 || start.y == 0 || start.x == r - 1 || start.y == c - 1) {
        printf("%d\n", start.step + 1);
        return;
    }
    Q[0].push(start);
    int num = 0;
    while (Q[0].size()) {
        num ^= 1;
        int flag = (int)Q[num].size();
        while(flag --) {
            node now = Q[num].front();
            Q[num].pop();
            for(int i = 0; i < 4; i++) {
                node next = now;
                next.x = now.x + dir[i][0];
                next.y = now.y + dir[i][1];
                next.step = now.step + 1;
                if (next.x < 0 || next.x >= r || next.y < 0 || next.y >= c)
                    continue;
                if (vis[next.x][next.y] == true || M[next.x][next.y] == '#')
                    continue;
                if (num == 0 && (next.x == 0 || next.x == r - 1
                              || next.y == 0 || next.y == c - 1)) {
                    printf("%d\n", next.step + 1);
                    return;
                }
                Q[num].push(next);
                vis[next.x][next.y] = true;
                if (vis[start.x][start.y] == false)
                vis[start.x][start.y] = true;
            }
        }
    }
    printf("IMPOSSIBLE\n");
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        while (Q[0].size())
            Q[0].pop();
        while (Q[1].size())
            Q[1].pop();
        memset(vis, 0, sizeof(vis));
        scanf("%d%d", &r, &c);
        node Begin;
        for (int i = 0; i < r; i++) {
            scanf("%s", M[i]);
            for (int j = 0; j < c; j++) {
                if (M[i][j] == 'J') {
                    Begin.x = i;
                    Begin.y = j;
                    Begin.step = 0;
                } else if (M[i][j] == 'F') {
                    node F(i, j, 0);
                    vis[i][j] = true;
                    Q[1].push(F);
                }
            }
        }
        bfs(Begin);
    }
    return 0;
}

K.POJ3984 迷宫问题

普通的4方向地图搜索,存路径两种方式,一种直接在节点存字符串记录之前所有步骤,找到结果输出,另一种记录上个节点到这步的操作和前驱即上个节点是谁,最后从目标节点回溯到根节点输出。

#include <cstdio>
#include <cstring>
#include <vector>
#include <utility>
using namespace std;

typedef pair<int, int> PII;

int m[5][5];
int dir[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool vis[5][5];

struct node {
    PII point;
    int pre;
};

vector<node> Q;
int step;

void outPut(int pos) {
    if (Q[pos].pre == -1) {
        printf("(0, 0)\n");
        return;
    }
    else outPut(Q[pos].pre);
    printf("(%d, %d)\n", Q[pos].point.first, Q[pos].point.second);
}

void bfs() {
    memset(vis, 0, sizeof(vis));
    node now;
    now.point = PII(0, 0);
    now.pre = -1;
    vis[now.point.first][now.point.second] = true;
    Q.push_back(now);
    step = -1;
    while (Q.size()) {
        step++;
        for (int i = 0; i < 4; i++) {
            node next = Q[step];
            next.point.first += dir[i][0];
            next.point.second += dir[i][1];
            next.pre = step;

            if(0 <= next.point.first && next.point.first <= 4 && 0 <= next.point.second &&
             next.point.second <= 4 && m[next.point.first][next.point.second] == 0 &&
             vis[next.point.first][next.point.second] == false) {
                vis[next.point.first][next.point.second] = true;
                Q.push_back(next);
                if (next.point == PII(4, 4)) {
                    outPut(Q.size() - 1);
                    return;
                }
            }
        }
    }
}

int main()
{
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            scanf("%d", &m[i][j]);
    bfs();
    return 0;
}

L.HDU1241 Oil Deposits

算油田数量,每找到一个油田直接把它填上,ans+1,继续找下个油田。

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;

string oil[105];
int m, n;

int dir[8][2] = { {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};

void dfs(int x, int y) {
    oil[x][y] = '*';
    for (int i = 0; i < 8; i++) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if (0 <= nx && nx < m && 0 <= ny && ny < n && oil[nx][ny] == '@')
            dfs(nx, ny);
    }
}

int main()
{
    while (scanf("%d%d", &m, &n) != EOF) {
        if (m == 0 && n == 0)
            break;
        for (int i = 0; i < m; i++)
            cin >> oil[i];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (oil[i][j] == '@') {
                    dfs(i, j);
                    ans++;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

M.HDU1495 非常可乐

有一个杯子可以装一半的可乐就算找到,注意如果此时三个杯子都有可乐的话还得再倒一次。

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

int S, N, M;
bool vis[105][105][105];

struct node {
    int S;
    int N;
    int M;
    int step;
};

void pour(int &from, int &to, int toSize) {
    if (from <= toSize - to) {
        to += from;
        from = 0;
    } else {
        from -= toSize - to;
        to = toSize;
    }
}

void bfs() {
    memset(vis, 0, sizeof(vis));
    queue<node> Q;
    node now;
    now.S = S;
    now.N = 0;
    now.M = 0;
    now.step = 0;
    vis[now.S][now.N][now.M] = true;
    Q.push(now);
    while (Q.size()) {
        now = Q.front();
        Q.pop();
        for (int i = 0; i < 6; i++) {
            node next = now;
            if (i == 0)
                pour(next.S, next.N, N);
            else if (i == 1)
                pour(next.S, next.M, M);
            else if (i == 2)
                pour(next.N, next.S, S);
            else if (i == 3)
                pour(next.N, next.M, M);
            else if (i == 4)
                pour(next.M, next.S, S);
            else
                pour(next.M, next.N, N);
            next.step = now.step + 1;

            if (vis[next.S][next.N][next.M] == false) {
                vis[next.S][next.N][next.M] = true;
                Q.push(next);
                if (next.S == S / 2 || next.N == S / 2 || next.M == S / 2) {
                    printf("%d\n", next.step + (next.S && next.N && next.M != 0));
                    return;
                }
            }
        }
    }
    printf("NO\n");
}

int main()
{
    while (scanf("%d%d%d", &S, &N, &M) != EOF) {
        if (S == 0)
            break;
        if (S & 1)
            printf("NO\n");
        else
            bfs();
    }
    return 0;
}

N.HDU2612 Find a way

不能用KFC来bfs,如果KFC数量很多就会超时。只要分别从Y、M两次bfs记录下到各KFC的时间,最后取最小。

#include <cstdio>
#include <utility>
#include <queue>
#include <map>
#include <vector>
using namespace std;

#define INF 1e6

typedef pair<int, int> PII;

int n, m;
char road[205][205];
PII Y, M;
map<PII, int> ans[2];

int dir[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0}};

struct node {
    PII point;
    int step;
};

void bfs(PII a, int person) {
    queue<node> Q;
    map<PII, bool> vis;
    node now;
    now.point = a;
    now.step = 0;
    vis[now.point] = true;
    Q.push(now);
    while (Q.size()) {
        now = Q.front();
        Q.pop();

        for (int i = 0; i < 4; i++) {
            node next;
            next.point.first = now.point.first + dir[i][0];
            next.point.second = now.point.second + dir[i][1];
            next.step = now.step + 1;

            if (0 <= next.point.first && next.point.first <= n && 0 <= next.point.second &&
             next.point.second <= m && road[next.point.first][next.point.second] != '#' &&
             vis[next.point] == false) {
                vis[next.point] = true;
                Q.push(next);
                if (road[next.point.first][next.point.second] == '@') {
                    ans[person][next.point] = next.step;
                }
            }
        }
    }
}

int main()
{
    while (scanf("%d%d", &n, &m) != EOF) {
        for (int i = 0; i < 2; i++) {
            ans[i].clear();
        }
        vector<PII> v;
        for (int i = 0; i < n; i++) {
            scanf("%s", road[i]);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (road[i][j] == 'Y') {
                    Y.first = i;
                    Y.second = j;
                } else if (road[i][j] == 'M') {
                    M.first = i;
                    M.second = j;
                } else if (road[i][j] == '@') {
                    v.push_back(PII(i, j));
                }
            }
        }

        bfs(Y, 0);
        bfs(M, 1);

        int Ans = INF;
        for (int i = 0; i < v.size(); i++) {
            int temp = ans[0][v[i]] + ans[1][v[i]];
            if (ans[0][v[i]] != 0 && ans[1][v[i]] != 0 && temp < Ans)
                Ans = temp;
        }
        printf("%d\n", Ans * 11);
    }
    return 0;
}