连连看

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1010;

int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};

int n, m;
int g[N][N];
bool st[N][N];
int X1, Y1, X2, Y2;

struct node {
    int x, y;
    int step;
};

void bfs(int a, int b) {
    queue<node> q;
    node One, next;
    One.x = a, One.y = b, One.step = -1;
    q.push(One);
    st[a][b] = true;

    while (q.size()) {
        auto t = q.front();
        q.pop();

        if (t.x == X2 && t.y == Y2 && t.step <= 2) {
            puts("YES");
            return;
        }

        for (int i = 0; i < 4; i ++ ) {

            next.x = t.x + dx[i], next.y = t.y + dy[i];
            next.step = t.step + 1;

            while (next.x >= 1 && next.x <= n && next.y >= 1 && next.y <= m && !g[next.x][next.y]) {
                if (!st[next.x][next.y]) {
                    st[next.x][next.y] = true;
                    q.push(next);
                }

                next.x = next.x + dx[i], next.y = next.y + dy[i];
            }
        }
    }

    puts("NO");  // 存在搜索完找不到答案的情况
    return;
}

int main() {
    while (cin >> n >> m) {
        if (n == 0 && m == 0)
            break;

        for (int i = 1; i <= n; i ++ )

            for (int j = 1; j <= m; j ++ )

                cin >> g[i][j];
        int q;
        cin >> q;

        while (q -- ) {
            memset(st, false, sizeof st);
            cin >> X1 >> Y1 >> X2 >> Y2;

            if (g[X1][Y1] != g[X2][Y2]) {
                puts("NO");
                continue;
            } else if (!g[X1][Y1] && !g[X2][Y2]) {
                puts("NO");
                continue;
            } else {
                int t = g[X1][Y1]; // 保存地图的原貌
                g[X1][Y1] = g[X2][Y2] = 0;
                bfs(X1, Y1);
                g[X1][Y1] = g[X2][Y2] = t;
            }
        }
    }

    return 0;
}

Oil Deposits

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[] = {0, 0, -1, 1, -1, 1, -1, 1};

int n, m;
char g[N][N];
bool st[N][N];

void dfs(int x, int y) {
    for (int i = 0; i < 8; i ++ ) {

        int nx = x + dx[i], ny = y + dy[i];

        if (!st[nx][ny] && nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] == '@') {
            st[nx][ny] = true;
            g[nx][ny] = '*';
            dfs(nx, ny);
        }
    }
}

int main() {
    while (cin >> n >> m) {
        if (n == 0)
            break;

        for (int i = 1; i <= n; i ++ )

            for (int j = 1; j <= m; j ++ )

                cin >> g[i][j];
        int ans = 0;
        memset(st, false, sizeof st);

        for (int i = 1; i <= n; i ++ )

            for (int j = 1; j <= m; j ++ ) {

                if (g[i][j] == '@') {
                    g[i][j] = '*';
                    ans ++ ;
                    dfs(i, j);
                }
            }

        cout << ans << endl;
    }

    return 0;
}

迷宫问题

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 10;

int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

int n, m;
int g[N][N];
bool st[N][N];
PII load[N][N];

void bfs(int a, int b) {
    queue<PII> q;
    PII One, next;
    One.first = a, One.second = b;
    q.push(One);
    st[a][b] = true;

    while (q.size()) {
        PII t = q.front();
        q.pop();

        for (int i = 0; i < 4; i ++ ) {

            next.first = t.first + dx[i], next.second = t.second + dy[i];

            if (next.first >= 0 && next.first <= 4 && next.second >= 0 && next.second <= 4 && !st[next.first][next.second]
                    && !g[next.first][next.second]) {
                st[next.first][next.second] = true;
                q.push(next);
                load[next.first][next.second] = t;
            }
        }
    }
}

void output(PII s) {
    if (s.first == s.second && s.first == 0) {
        printf("(0, 0)\n");
        return;
    }

    output(load[s.first][s.second]);
    printf("(%d, %d)\n", s.first, s.second);
}

int main() {
    for (int i = 0; i < 5; i ++ )

        for (int j = 0; j < 5; j ++ )

            cin >> g[i][j];
    bfs(0, 0);
    PII ans;
    ans.first = ans.second = 4;
    output(ans);
    return 0;
}