P1451題解 用dfs（深搜）+二維數組求解（c++代碼）

先介紹一下dfs：

dfs是一種搜尋方式，也就是深度搜尋

假如有一個迷宮，要找到出口，可以先去一條路一條路試錯，錯了就傳回之前的分叉路口，

再試錯，探索，進而找到出口。

代碼如下        

a代表細胞資料

void dfs(int x,int y){

        a[x][y]=0;//已經探索過了

        if(a[x-1][y]>0)dfs(x-1,y);//向上走

        if(a[x+1][y]>0)dfs(x+1,y);//向下走

        if(a[x][y+1]>0)dfs(x,y+1);//向右走

        if(a[x][y-1]>0)dfs(x,y-1);//向左走;

}

進入正題

整體思路如下

______________________________________________________

1 周遊二維數組每一個點，如果是細胞數字，sum++，進行dfs深搜。

2 搜尋的時候将細胞數字改成零，然後去找相鄰的細胞數字，

進而将一個大細胞全部清零,防止下次在通路。

3 輸出sum

_______________________________________________________

這裡要注意輸入的時候數字與數字之間沒有空格

格式化輸入scanf("%1d",&a[i][j]);

假如讀入123 他隻會讀入1 因為域寬隻有1，如果接下來還有讀入的話，會給後面的讀入；

AC代碼

#include<bits/stdc++.h>
using namespace std;
int a[105][105],n,m,sum;
void dfs(int x,int y){
	a[x][y]=0;
	if(a[x-1][y]>0)dfs(x-1,y);
	if(a[x][y+1]>0)dfs(x,y+1);
	if(a[x+1][y]>0)dfs(x+1,y);
	if(a[x][y-1]>0)dfs(x,y-1);
}
int main(){                     
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%1d",&a[i][j]);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]>0){sum++;dfs(i,j);}
		}
	}
	cout<<sum;
}
           

這是我第一篇題解有什麼不對的希望大神指出；