ZOJ 1047 Image Perimeters：DFS 求聯通塊周長

題目簡介

給定字符網格（'.' 空地，'X' 物體），從指定點 (r,c) 開始，八方向連通的 'X' 形成一個物體。求該物體周長（每個格子邊長 1，相鄰共享邊不計入周長）。網格 ≤ 20×20。

解題思路

DFS 搜索聯通塊：

• 從起點開始，八方向擴展（上下左右+四對角）。
• 每個 'X' 初始貢獻周長 4，四直角方向（上下左右）每有一個相鄰 'X'，周長 -1。
• 對角相鄰不共享邊，不影響周長。
• 遞歸搜索並累加周長，標記訪問避免重複。

代碼實現

#include <iostream>
#include <cstring>
using namespace std;
const int N = 25;
char grid[N][N];
bool vis[N][N];
int n, m, sr, sc, ans;
int dir[8][2] = {{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{-1,1},{1,-1},{1,1}};

void dfs(int x, int y) {
    if (vis[x][y]) return;
    vis[x][y] = true;
    int cnt = 4;
    for (int i=0;i<8;i++) {
        int nx=x+dir[i][0], ny=y+dir[i][1];
        if (nx<0||nx>=n||ny<0||ny>=m||grid[nx][ny]!='X') continue;
        dfs(nx, ny);
        if (dir[i][0]==0 || dir[i][1]==0) cnt--; // 直角相鄰
    }
    ans += cnt;
}

int main() {
    while (cin >> n >> m >> sr >> sc, n||m||sr||sc) {
        sr--; sc--;
        memset(vis, 0, sizeof(vis));
        for (int i=0;i> grid[i];
        ans = 0;
        dfs(sr, sc);
        cout << ans << endl;
    }
    return 0;
}

複雜度分析

網格 ≤ 400 格，DFS 瞬間完成。