輸入一個n*n的黑白圖像（1表示黑色，0表示白色），任務(wù)是統(tǒng)計其中八連塊的個數(shù)。如果兩個黑格子有公共邊或者公共頂點，就說它們屬于同一個八連塊。如圖6-11所示的圖形有3個八連塊。

?	?	?	?	?	?
?	?	?	?	?	?
?	?	?	?	?	?
?	?	?	?	?	?
?	?	?	?	?	?
?	?	?	?	?	?

圖6-11? 擁有3個八連塊的黑白圖形

【分析】

用遞歸求解：從每個黑格子出發(fā)，遞歸訪問它所有的相鄰黑格。

int mat[MAXN][MAXN], vis[MAXN][MAXN]; void dfs(int x, int y) {if(!mat[x][y] || vis[x][y]) return; // 曾經(jīng)訪問過這個格子，或者當前格子是白色vis[x][y] = 1; // 標記(x,y)已訪問過dfs(x-1,y-1); dfs(x-1,y); dfs(x-1,y+1);dfs(x-1,y); dfs(x,y+1);dfs(x+1,y-1); dfs(x+1,y); dfs(x+1,y+1); // 遞歸訪問周圍的八個格子 } 這里，黑格(x,y)的mat[x][y]為1，白格為0。為了避免同一個格子訪問多次，用標志vis[x][y]記錄格子(x,y)是否訪問過。在輸入之前，在迷宮的外面加上一圈虛擬的白格子，見下面的程序。 memset(mat, 0, sizeof(mat)); //所有格子都初始化為白色,包括周圍一圈的虛擬格子 memset(vis, 0, sizeof(vis)); // 所有格子都沒有訪問過 scanf("%d", &n); for(int i = 0; i < n; i++) {scanf("%s", s);for(int j = 0; j < n; j++)mat[i+1][j+1] = s[j]-'0'; // 把圖像往中間移動一點，空出一圈白格子 }

?

接下來，只需不斷找黑格，然后調(diào)用dfs。從它出發(fā)尋找八連塊：

int count = 0; for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(!vis[i][j] && mat[i][j]) { count++; dfs(i,j); } //找到?jīng)]有訪問過的黑格 printf("%d\n", count);

?

完整的程序如下：

#include <stdio.h> #include <string.h> const int MAXN = 1000; int n;int mat[MAXN][MAXN], vis[MAXN][MAXN]; void dfs(int x, int y) {if(!mat[x][y] || vis[x][y]) return; //曾經(jīng)訪問過這個格子，或者當前 格子是白色 vis[x][y] = 1; // 標記(x,y)已訪問過dfs(x-1,y-1); dfs(x-1,y); dfs(x-1,y+1);dfs(x-1,y); dfs(x,y+1);dfs(x+1,y-1); dfs(x+1,y); dfs(x+1,y+1); // 遞歸訪問周圍的八個格子 }int main() {char s[MAXN + 10];memset(mat, 0, sizeof(mat)); // 所有格子都初始化為白色，包括周圍 一圈的虛擬格子memset(vis, 0, sizeof(vis)); // 所有格子都沒有訪問過scanf("%d", &n);for(int i = 0; i < n; i++) {scanf("%s", s);for(int j = 0; j < n; j++)mat[i+1][j+1] = s[j]-'0'; // 把圖像往中間移動一點，空出一圈白格子}int count = 0;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)// 找到?jīng)]有訪問過的黑格if(!vis[i][j] && mat[i][j]) { count++; dfs(i,j); } printf("%d\n", count);return 0; }

?

上面的函數(shù)dfs就是深度優(yōu)先遍歷（Depth-FirstSearch，DFS）的算法，DFS和BFS一樣，都是從一個結(jié)點出發(fā)，按照某種特定的次序訪問圖中的其他特點。不同的是，BFS使用隊列來存放待擴展結(jié)點，而DFS使用的是棧。

?

附：我自己理解后敲的代碼：

#include <stdio.h> #include <string.h> #include<algorithm> #include<iostream> #define M 1020 using namespace std; int n; int i,j; char map[M][M]; void dfs(int x,int y) {if(map[x][y]!='1'||x<0||y<0||x>=n||y>=n)return; //曾經(jīng)訪問過這個格子，或者當前格子是白色else{map[x][y] = '0'; // 標記(x,y)已訪問過dfs(x-1,y-1);dfs(x-1,y+1);dfs(x-1,y);dfs(x,y+1);dfs(x,y-1);dfs(x+1,y-1);dfs(x+1,y);dfs(x+1,y+1); // 遞歸訪問周圍的八個格子} }int main() {memset(map, 0, sizeof(map)); // 所有格子都沒有訪問過scanf("%d", &n);for(i=0; i<n; i++)for(j=0; j<n; j++)cin>>map[i][j];int count = 0;for(i = 0; i <n; i++)for(j = 0; j <n; j++){// 找到?jīng)]有訪問過的黑格if(map[i][j]=='1'){dfs(i,j);count++;}}printf("%d\n", count);return 0; } /* 6 100100 001010 000000 110000 111000 010100 */

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/dyllove98/p/3226233.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

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

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