输出路径

走迷宫输出路径

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define x first
#define y second

const int N = 20;
char g[N][N];
typedef pair<int, int> PII;
vector<PII> res;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, m;
bool st[N][N], flag;
int x1, y1, x2, y2;

void dfs(int x, int y)
{
    st[x][y] = true;
    if(x == x2 && y == y2)
    {
        flag = true;
        printf("(%d,%d)",x1,y1);
        for (int i = 1; i < res.size() - 1; i ++ )
            printf("->(%d,%d)",res[i].x, res[i].y);
        printf("->(%d,%d)\n",x2,y2);
    }
    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if(a<1 || a>n || b<1 || b>m || st[a][b] || g[a][b]=='0') continue;
        st[a][b] = true;
        res.push_back({a, b});
        dfs(a, b);
        res.pop_back();
        st[a][b] = false;
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= m; j ++ )
            cin >> g[i][j];
    cin >> x1 >> y1;
    cin >> x2 >> y2;

    res.push_back({x1, y1});
    dfs(x1, y1);
    if(!flag) cout << -1;
    return 0;
}

求解岛屿数量

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

typedef pair<int, int> PII;

const int N = 60;
char g[N][N];
int n, m;
vector<vector<PII>> islands; // 存储所有岛屿的坐标

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

void dfs(int x, int y, vector<PII>& p)
{
    g[x][y] = '.'; // 标记当前位置已经被访问过
    p.push_back({x, y});
    for (int i = 0; i < 4; i++)
    {
        int a = dx[i] + x, b = dy[i] + y;
        if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == '#')
            dfs(a, b, p);
    }
}

int main()
{
    cin >> n;
    m = n; // n x n 的矩阵
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> g[i][j];

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (g[i][j] == '#')
            {
                vector<PII> island;
                dfs(i, j, island);
                islands.push_back(island);
            }
        }
    }

    cout << "Number of islands: " << islands.size() << endl;

    // 打印岛屿的位置
    for (int i = 0; i < islands.size(); i++)
    {
        cout << "Island " << i + 1 << " coordinates:" << endl;
        for (int j = 0; j < islands[i].size(); j++)
        {
            cout << islands[i][j].first << " " << islands[i][j].second << endl;
        }
        cout << endl;
    }

    return 0;
}