首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

POJ 1979:紅色警戒區域計數 - 經典 DFS 洪水填充

     編輯:關於C++

問題描述

給定 n×m 网格(n,m ≤ 20),@ 為起點,. 為可通過,# 為障礙。求從起點出發能到達的格子數(含起點)。多組測試,以 0 0 結束。

DFS 洪水填充模板

標準四方向 DFS,訪問標記為 # 避免重複。邊界檢查:0 ≤ nx < n, 0 ≤ ny < m。

代碼實現

#include <iostream>
using namespace std;
int n, m, sx, sy, cnt;
char g[25][25];
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};

void dfs(int x, int y) {
    cnt++;
    g[x][y] = '#';
    for (int i=0;i<4;i++) {
        int nx=x+dx[i], ny=y+dy[i];
        if (nx>=0 && nx=0 && ny>m>>n, n||m) {
        cnt=0;
        for (int i=0;i>g[i][j];
            if (g[i][j]=='@') sx=i, sy=j;
        }
        dfs(sx,sy);
        cout<

關鍵點

  • 輸入順序:先 m(列),後 n(行)。
  • 網格存儲為 char g[25][25],下標 [行][列]。
  • 遞歸深度最大 400,棧安全。
  • 直接修改網格標記訪問,無需額外 vis 數組。

複雜度

O(n*m) 每測試用例,瞬間通過。

總結

POJ 1979 是 DFS 連通區域計數的入門必刷題。掌握「四方向數組 + 邊界檢查 + 就地標記」的標準模板,可秒殺所有網格搜索基礎題。

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved