kuangbin 1 简单搜索

#include <iostream>
using namespace std;
const int maxn = 33;
int n, m, k, bgn, bgm, bgk, edn, edm, edk, dir[6][3] = {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}}, vis[maxn][maxn][maxn], flag;
char mp[maxn][maxn][maxn];
#include <cstring>
#define cl(a, b) memset(a, b, sizeof(a))

struct node {
    int x, y, k, step;
    node(int x, int y, int k, int step):x(x), y(y), k(k), step(step){}
};

#include <queue>
queue<node> q;
void bfs() {
    vis[bgn][bgm][bgk] = 1;
    q.push(node(bgn, bgm, bgk, 0));
    while (!q.empty()) {
        node nw = q.front();q.pop();
        if (nw.x == edn && nw.y == edm && nw.k == edk) {flag = 1;printf("Escaped in %d minute(s).\n", nw.step); return;}
        for (int i = 0; i < 6; ++i) {
            int nx = nw.x+dir[i][0], ny = nw.y+dir[i][1], nk = nw.k+dir[i][2];
            if (!vis[nx][ny][nk] && (mp[nx][ny][nk] == '.' || mp[nx][ny][nk] == 'E') && nx >= 0 && nx < n && ny >= 0 && ny < m && nk >= 0 && nk < k) {vis[nx][ny][nk] = 1;q.push(node(nx, ny, nk, nw.step+1));}
        }
    }
}

int main() {
    while (~scanf("%d%d%d", &n, &m, &k) && n && m && k) {
        // init
        cl(vis, 0);flag = 0;
        while (!q.empty()) q.pop();
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                scanf("%s", mp[i][j]);
        // find bg&ed point
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                for (int l = 0; l < k; ++l)
                    if (mp[i][j][l] == 'S') bgn = i, bgm = j, bgk = l;
                    else if (mp[i][j][l] == 'E') edn = i, edm = j, edk = l;
        bfs();
        if (!flag) printf("Trapped!\n");
    }
    return 0;
}

#include <iostream>
using namespace std;
int mp[6][6], dir[4][2]={{0, 1}, {0, -1}, {1, 0}, {-1, 0}}, vis[6][6];

struct node {
    int x, y;
    node * pre;
};

#include <vector>
vector<pair<int, int>> b;
void printtrack(node * nw) {
    while (nw) {
        b.push_back(make_pair(nw->x, nw->y));
        nw = nw->pre;
    }
    for (int i = b.size()-1; i >= 0; --i) printf("(%d, %d)\n", b[i].first-1, b[i].second-1);
}

#include <queue>
queue<node *> q;
void bfs(){
    vis[1][1] = 1;
    node * tmnode = new node;
    tmnode->x = 1, tmnode->y = 1, tmnode->pre = NULL;
    q.push(tmnode);
    while (!q.empty()) {
        node * nw = q.front();q.pop();
        if (nw->x == 5 && nw->y == 5) {printtrack(nw);return;}
        for (int i = 0; i < 4; ++i) {
            int nx = nw->x+dir[i][0], ny = nw->y+dir[i][1];
            if (!vis[nx][ny] && !mp[nx][ny] && nx >= 1 && nx <= 5 && ny >= 1 && ny <= 5) {
                node * ntnode = new node();
                ntnode->x = nx, ntnode->y = ny;ntnode->pre = nw;
                vis[nx][ny] = 1; q.push(ntnode);
            }
        }
    }
}

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

#include <iostream>
using namespace std;
const int maxn = 105;
int n, m, cnt, dir[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
char mp[maxn][maxn];

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

int main() {
    while (~scanf("%d%d", &n, &m) && n && m) {
        // init
        cnt = 0;
        for (int i = 0; i < n; ++i) scanf("%s", mp[i]);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if (mp[i][j] == '@') {cnt++;dfs(i, j);}
                printf("%d\n", cnt);
    }
    return 0;
}