技術文章 » DFS(思路加簡單例題)

DFS(思路加簡單例題)

2020-10-13 13:00:34

DFS(思路加簡單例題)

dfs即深度優先搜尋，就是隻要我還能走，我就一條路走到頭,直到我最後不能走的時候我再回頭去找別的路。

深度優先搜尋遍歷連通圖
1）從圖中某個頂點出發，存取x，並置mp[x]的值為true.
2) 依次檢查x的所有的鄰接點w，如果mp[w]的值為false,再從w出發進行遞迴遍歷，直至圖中所有的頂點都被存取過。

/*
void dfs()
{
 if(判斷條件)
 return ;
	for(拓展狀態)
	{
		判斷合法
		記錄
		dfs(繼續搜);
		回溯;
	}
}
*/

一，走迷宮型別

題目描述

小明現在在玩一個遊戲，遊戲來到了教學關卡，迷宮是一個NM的矩陣.

小明的起點在地圖中用「S」來表示，終點用「E」來表示，障礙物用「#」來表示，空地用「.」來表示。

障礙物不能通過。小明如果現在在點（x，y）處，那麼下一步只能走到相鄰的四個格子中的某一個：（x+1，y），（x-1，y），（x，y+1），（x，y-1）；

小明想要知道，現在他能否從起點走到終點。

輸入描述:

本題包含多組資料。
每組資料先輸入兩個數位N,M
接下來N行，每行M個字元，表示地圖的狀態。
資料範圍：
2<=N,M<=500
保證有一個起點S，同時保證有一個終點E.

輸出描述:

每組資料輸出一行，如果小明能夠從起點走到終點，那麼輸出Yes，否則輸出No

範例1

輸入

3 3
S..
..E
...
3 3
S##
###
##E

輸出

Yes
No

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[505][505],mp[505][505];
int aa[4][2]={1,0,-1,0,0,1,0,-1};
int xx,yy,x,y;
void dfs(int i,int j)
{
	if(i==x&&j==y)
	return ;//找到出口，從遞迴出來
	mp[i][j]=1;//標記走過的地方
	for(int k=0;k<=3;k++)
	{
		int dx=i+aa[k][0];
		int dy=j+aa[k][1];
		if(a[dx][dy]!='#'&&dx>0&&dx<=n&&dy>0&&dy<=m&&!mp[dx][dy])//判斷是否能走
		{
			mp[dx][dy]=1;
			dfs(dx,dy);//繼續走到下一步	
		}
	}
	
}
int main()
{
	while(cin>>n>>m)
	{
	int i,j;
	memset(mp,0,sizeof(mp));
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='S')//記錄起點
			xx=i,yy=j;
			 if(a[i][j]=='E')
			 x=i,y=j;//記錄終點
		}
	}
	dfs(xx,yy);
	if(mp[x][y])
	cout<<"Yes"<<endl;
	else
	cout<<"No"<<endl;
	}
	return 0;
}

二 ，選數，排列組合問題，暴力組合

題目描述

已知 n個整數 x1,x2,…, x n x_n xn​ 以及1個整數k(k<n)。從n個整數中任選k個整數相加，可分別得到一系列的和。例如當n=4,k=3,4個整數分別為3,7,12,19時，可得全部的組合與它們的和為：

3+7+12=22

3+7+19=29

7+12+19=38

3+12+19=34

現在，要求你計算出和為素數共有多少種。

例如上例，只有一種的和為素數：3+7+19=29

輸入格式

鍵盤輸入，格式為：

n,k(1≤n≤20,k<n)

x1,x2,…, x n x_n xn​(1≤xi≤5000000)

輸出格式

螢幕輸出，格式為： 1個整數（滿足條件的種數）。

輸入輸出樣例

輸入 #1

4 3
3 7 12 19

輸出 #1

1

#include<bits/stdc++.h>
using namespace std;   
int a[10000],sum=0,ans=0;  
int n,k;
int sushu(int f)
{
 for(int i=2;i<=sqrt(f);i++)
 {
     if(f%i==0)
     return 0;
 }
 return 1;
}
void dfs(int t,int x)//t表示還差多少個選到k個，x表示選到a【x】。
{
  if(t==0)
  ans+=sushu(sum);
  else
  {
      x++;
    for(int i=x;i<=n;i++)
    {
      sum+=a[i];
      t--;
      dfs(t,i);
      sum-=a[i];//回溯
      t++;
    }

  }
  

}
int main()
{

    cin>>n>>k;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    dfs(k,0);
    cout<<ans<<endl;
    getchar();
    getchar();
return 0;
}

三，連通性

題目描述

一矩形陣列由數位 0到 9組成，數位 1 到 9 代表細胞，細胞的定義為沿細胞數位上下左右若還是細胞數位則為同一細胞，求給定矩形陣列的細胞個數。

輸入格式

第一行兩個整數代表矩陣大小 n和 m。

接下來 n行，每行一個長度為 m的只含字元 0 到 9 的字串，代表這個 n×m 的矩陣。

輸出格式

一行一個整數代表細胞個數。

輸入輸出樣例

輸入 #1

4 10
0234500067
1034560500
2045600671
0000000089

輸出 #1

4

說明/提示

資料規模與約定

對於 100%的資料，保證 1≤n,m≤100。

#include<bits/stdc++.h> 
using namespace std;
int n,m,ans=0;
int a[105][105];
bool mp[105][105];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void dfs(int x,int y)//查詢與該點連通的點 
{
	mp[x][y]=1;
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(a[nx][ny]==0 || mp[nx][ny]==1) continue;
		dfs(nx,ny);
	}
}
int main()
{
	cin>>n>>m;
	memset(a,0,sizeof(a));
	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(mp[i][j]==0 && a[i][j]!=0)//找到未走過的不為0的數 
			{
				dfs(i,j);//將與這個數連通的全都標記為走過即為1 
				ans++;
			}
		}
	}
	cout<<ans;	
	return 0;
}