掃描統(tǒng)計是程序設(shè)計拓展求和的一個基本課題。

有一條封閉曲線劃定的地圖,界定曲線上的點用“1”表示,曲線內(nèi)外的點用“0”表示試實施圖形點掃描,統(tǒng)計地圖的面積(即“封閉”曲線內(nèi)的“0”點數(shù))。

1、設(shè)計要點

要統(tǒng)計用“1”標識的封閉曲線內(nèi)“0”點的點數(shù),關(guān)鍵在于如何識別哪些“0”點在封閉曲線內(nèi),哪些“0”點在封閉曲線外。

試對封閉曲線外的“0”點實施“擴散傳染”處理,處理成“2”點,以與曲線內(nèi)的“0”點相區(qū)別。考慮到連續(xù)曲線可能復雜的彎曲變化,用簡單一次枚舉檢測難以區(qū)分曲線內(nèi)與外的“0”,可
以把曲線外的“0”通過多次“擴散傳染”逐個變?yōu)椤?”,因為封閉曲線隔離使得曲線內(nèi)的“0”保持不變。
核心思想
(1)四周邊上的“0”無疑在曲線外,變?yōu)椤?”。
(2)凡與“2”相鄰的“0”點通過“傳染”變?yōu)椤?”。即判斷每一個“0”點,若它的上下左
右元素中有某一個為“2”點,即被擴散傳染為“2”
(3)約定掃描xy(即圖中點的個數(shù))次。設(shè)置變量w,每次掃描前,w=0;凡有擴散傳染
發(fā)生,w=1。每次掃描后檢驗,如果w=0,表示該次掃描沒有傳染發(fā)生,即停止。
(4)統(tǒng)計“0”的點數(shù)即為所求封閉曲線的面積。*

代碼：`

#include <iostream> #define maxn 666int n, m; void solve(int a[][maxn]) {n--;m--;long t = n * m ;int w;for (int i = 0; i <= m; i++) { //m為列數(shù) ，把邊上的0變成2if (a[0][i] == 0)a[0][i] = 2;if (a[n][i] == 0)a[n][i] = 2;}for (int i = 1; i < n; i++) { //n為行數(shù) ，把邊上的0變成2(因為前面已經(jīng)把兩行給初始化了if (a[i][0] == 0)a[i][0] = 2;if (a[i][m] == 0)a[i][m] = 2;}for (int k = 1; k < t; k++) {w = 0;for (int i = 1; i < n ; i++)for (int j = 1; j < m ; j++)if ((a[i - 1][j] == 2 || a[i + 1][j] == 2 || a[i][j - 1] == 2 || a[i][j + 1] == 2) && a[i][j] == 0) {a[i][j] = 2;w = 1;}if (w == 0) //表明整個滿足條件的點都沒了break;} }int main() {int map[maxn][maxn];int ans = 0;scanf("%d%d", &n, &m);for (int i = 0; i < n; i++)for (int j = 0; j < m; j++) {int a;scanf("%d", &a);map[i][j] = a;}solve(map);for (int i = 0; i <= n; i++) {for (int j = 0; j <= m ; j++) {printf("%d ", map[i][j]);if (map[i][j] == 0)ans++;}printf("\n");}printf("%d\n", ans);return 0; } /*12 12 0 0 0 1 0 0 0 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 */

總結(jié)

以上是生活随笔為你收集整理的地图处理（dfs算法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。