DFS【搜索1】
DFS模板
void dfs(int depth)//depth表示當(dāng)前的層數(shù)(或深度) { if(depth>n)//到達(dá)葉子節(jié)點(diǎn)，該路已走到盡頭 return; for(int i=1;i<=n;i++)//n表示最大的值，即最大深度為n { if(b[i]==0)//b數(shù)組表示探索的狀態(tài)，1表示已被探索，0表示尚未被探索 { b[i]=1;//標(biāo)記當(dāng)前的b[i]已被探索 a[level]=i;//記錄當(dāng)前的節(jié)點(diǎn)值 dfs(level+1);//進(jìn)一步的搜索 b[i]=0;//還原當(dāng)前的b[i]元素被探索的狀態(tài) } } }
數(shù)字型搜索
全排列問題
題目描述
排列與組合是常用的數(shù)學(xué)方法。
先給一個正整數(shù) ( 1 < = n < = 10 )
例如n＝3，所有組合,并且按字典序輸出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
輸入
輸入一個整數(shù)n( 1<=n<=10)
輸出
輸出所有全排列
每個全排列一行，相鄰兩個數(shù)用空格隔開（最后一個數(shù)后面沒有空格）
樣例輸入 Copy
3
樣例輸出 Copy
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
#include<bits/stdc++.h> #include<queue> using namespace std; const int N=100; typedef long long ll; int n,a[10010],b[10010]; void print() { for(int i=1;i<=n;i++) { printf("%5d",a[i]); } cout<<endl; } void dfs(int level) { if(level==n+1) { print(); return; } for(int i=1;i<=n;i++) { if(b[i]==0) { b[i]=1; a[level]=i; dfs(level+1); b[i]=0; } } } int main() { cin>>n; dfs(1); }
【牛客】 Factorial
1、暴力解題，代碼略；
2、dfs解題(重點(diǎn))，萬物皆可搜，有點(diǎn)類似斐波那契遞歸
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn=1e5+10; #define IO ios::sync_with_stdio(false), cin.tie(0) #define T int t ;cin >> t;while(t--) ll a[maxn]; ll dfs(ll n) { if(n<=1) { return 1; } else { return dfs(n-1)*n; } } int main() { T { ll n; scanf("%lld",&n); printf("%lld\n",dfs(n)); } }
地圖型搜索
n皇后問題
#include<bits/stdc++.h> using namespace std; typedef long long ll; int n,y[100010],s,ans[100010]; bool check(int x)//剪枝，判斷兩點(diǎn)的位置\\ 兩點(diǎn)的斜率的絕對值不得等于1；兩點(diǎn)不得在同一水平線上(包括同一行和同一列) { for(int i=1;i<x;i++)//i本身就是指行號，y[i]表示對應(yīng)的列號 { if(abs(x-i)==abs(y[x]-y[i])||y[x]==y[i]||x==i) { return 0; } } return 1; } void dfs(int num) { if(num>n)//越界處理 { s++; return; } for(int i=1;i<=n;i++) { y[num]=i;//將當(dāng)前的行號賦值給第num個皇后 if(check(num)) dfs(num+1);//進(jìn)行下一步的搜索 } } int main() { for(int i=1;i<=10;i++) { n=i; s=0; dfs(1); ans[i]=s; } while(~scanf("%d",&n)&&n) printf("%d\n",ans[n]); }
POJ3083 Children of the Candy Corn
左搜索(Ldfs)+右搜索(Rdfs)+最短路徑搜索(bfs)
搜索方位
左搜索：
始終靠左搜索，如果左邊是墻#，那就往上面搜索；上面是墻#，那就往右邊搜索；右邊是墻#則返回之前的位置，即往后搜索。
右搜索：
bfs最短路搜索：
創(chuàng)建隊(duì)列，在一個點(diǎn)的周圍的同一層搜索(這是與DFS的區(qū)別最大之處)，用vis數(shù)組標(biāo)記是否被搜索過
#include<bits/stdc++.h> typedef long long ll; using namespace std; const int N=55; char mp[41][41]; int vis[41][41]; int m,n,f,ans1,ans2; int head_x,head_y,tail_x,tail_y; int dir1[4][2]= {-1,0,1,0,0,1,0,-1}; struct node { int x,y,step; } head,tail; bool judge(int xx,int yy) { if(xx>=1&&xx<=m&&yy>=1&&yy<=n&&mp[xx][yy]!='#'&&vis[xx][yy]==0) return true; return false; } void dfs1(int xx,int yy,int step,int dir)//逆時針走法 { if(f==1) return; if(xx==tail_x&&yy==tail_y) { f=1; ans1=step; return; } if(dir==1)//右上左下 { if(judge(xx+1,yy)) dfs1(xx+1,yy,step+1,4); if(judge(xx,yy-1)) dfs1(xx,yy-1,step+1,1); if(judge(xx-1,yy)) dfs1(xx-1,yy,step+1,2); if(judge(xx,yy+1)) dfs1(xx,yy+1,step+1,3); } else if(dir==2)//上左下右 { if(judge(xx,yy-1)) dfs1(xx,yy-1,step+1,1); if(judge(xx-1,yy)) dfs1(xx-1,yy,step+1,2); if(judge(xx,yy+1)) dfs1(xx,yy+1,step+1,3); if(judge(xx+1,yy)) dfs1(xx+1,yy,step+1,4); } else if(dir==3)//左下右上 { if(judge(xx-1,yy)) dfs1(xx-1,yy,step+1,2); if(judge(xx,yy+1)) dfs1(xx,yy+1,step+1,3); if(judge(xx+1,yy)) dfs1(xx+1,yy,step+1,4); if(judge(xx,yy-1)) dfs1(xx,yy-1,step+1,1); } else//右下上左 { if(judge(xx,yy+1)) dfs1(xx,yy+1,step+1,3); if(judge(xx+1,yy)) dfs1(xx+1,yy,step+1,4); if(judge(xx,yy-1)) dfs1(xx,yy-1,step+1,1); if(judge(xx-1,yy)) dfs1(xx-1,yy,step+1,2); } } void dfs2(int xx,int yy,int step,int dir) { if(f==1) { return; } if(xx==tail_x&&yy==tail_y) { f=1; ans2=step; return; } if(dir==1) { if(judge(xx-1,yy)) dfs2(xx-1,yy,step+1,2); if(judge(xx,yy-1)) dfs2(xx,yy-1,step+1,1); if(judge(xx+1,yy)) dfs2(xx+1,yy,step+1,4); if(judge(xx,yy+1)) dfs2(xx,yy+1,step+1,3); } else if(dir==2) { if(judge(xx,yy+1)) dfs2(xx,yy+1,step+1,3); if(judge(xx-1,yy)) dfs2(xx-1,yy,step+1,2); if(judge(xx,yy-1)) dfs2(xx,yy-1,step+1,1); if(judge(xx+1,yy)) dfs2(xx+1,yy,step+1,4); } else if(dir==3) { if(judge(xx+1,yy)) dfs2(xx+1,yy,step+1,4); if(judge(xx,yy+1)) dfs2(xx,yy+1,step+1,3); if(judge(xx-1,yy)) dfs2(xx-1,yy,step+1,2); if(judge(xx,yy-1)) dfs2(xx,yy-1,step+1,1); } else { if(judge(xx,yy-1)) dfs2(xx,yy-1,step+1,1); if(judge(xx+1,yy)) dfs2(xx+1,yy,step+1,4); if(judge(xx,yy+1)) dfs2(xx,yy+1,step+1,3); if(judge(xx-1,yy)) dfs2(xx-1,yy,step+1,2); } } int bfs() { queue<node> q; while(!q.empty()) { q.pop(); } head.x=head_x,head.y=head_y,head.step=1; q.push(head); vis[head_x][head_y]=1; while(!q.empty()) { head=q.front(); q.pop(); if(head.x==tail_x&&head.y==tail_y) { return head.step; } for(int i=0; i<4; i++) { tail.x=head.x+dir1[i][0]; tail.y=head.y+dir1[i][1]; if(judge(tail.x,tail.y)) { tail.step=head.step+1; vis[tail.x][tail.y]=1; q.push(tail); } } } return 0; } int main() { int T; scanf("%d",&T); while(T--) { memset(vis,0,sizeof vis); scanf("%d%d",&n,&m); for(int i=1; i<=m; i++) { for(int j=1; j<=n; j++) { scanf(" %c",&mp[i][j]); if(mp[i][j]=='S') { head_x=i; head_y=j; } if(mp[i][j]=='E') { tail_x=i; tail_y=j; } } } f=0; ans1=0; dfs1(head_x,head_y,1,1); f=0; ans2=0; dfs2(head_x,head_y,1,1); int ans3=bfs(); printf("%d %d %d\n",ans1,ans2,ans3); } }
棋盤問題
n表示棋盤的大小是n*n，m表示棋子的數(shù)量，結(jié)束dfs的條件就是當(dāng)前的棋子數(shù)量大于等于m(因?yàn)槌跏嫉?就已經(jīng)存在1顆棋子了)。
#include<iostream> #include<algorithm> #include<string> #include<string.h> #define IO ios::sync_with_stdio(false), cin.tie(0) typedef long long ll; using namespace std; const ll maxn=1e5+10; char mp[100][100]; bool vis[100]; ll n,m,s; void dfs(ll x,ll y) { if(y>=m) { s++; return; } for(ll i=x; i<n; i++) for(ll j=0; j<n; j++) { if(vis[j]==false&&mp[i][j]=='#') { vis[j]=true; dfs(i+1,y+1); vis[j]=false; } } } int main() { while(1) { scanf("%lld%lld",&n,&m); if(n==-1&&m==-1) break; memset(vis,0,sizeof vis); memset(mp,0,sizeof mp); for(ll i=0; i<n; i++)scanf("%s",mp[i]); s=0; dfs(0,0); cout<<s<<endl; } }
Oil Deposit
#include <bits/stdc++.h> using namespace std ; typedef long long ll; ll m,n; char mp[110][110]; ll dir[8][2]= { {0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1} };//方向可以任意，當(dāng)前方向見圖 void dfs(ll x,ll y) { mp[x][y]='*';//把當(dāng)前的@轉(zhuǎn)換成*，避免重復(fù)查找 for(ll i=0; i<8; i++) { ll xx=x+dir[i][0],yy=y+dir[i][1]; if(xx>=1&&xx<=m&&yy>=1&&yy<=n&&mp[xx][yy]=='@') { dfs(xx,yy); } } return;//遞歸結(jié)束 } int main() { while(~scanf("%lld%lld",&m,&n)&&n&&m) { ll sum=0; for(ll i=1; i<=m; i++) { for(ll j=1;j<=n;j++) { cin>>mp[i][j]; //scanf(" %c",&mp[i][j]); //兩種讀入方式均可，要注意的是，用scanf()讀入的話，需要在%c之前加入一個空格，這是專門用來吸收"\n" } } for(ll i=1; i<=m; i++) { for(ll j=1; j<=n; j++) { if(mp[i][j]=='@') { dfs(i,j); sum++; } } } cout<<sum<<endl; } }
Red and Black
用dfs搜索最長路，黑磚可走，紅磚不可走，@表示出發(fā)點(diǎn)，輸出最大黑磚數(shù)
#include<iostream> #include<string> #include<cstdio> using namespace std; typedef long long ll; ll m,n; char mp[25][25]; ll dir[4][2]={ {-1,0},{1,0},{0,-1},{0,1} }; ll s; void dfs(ll x,ll y) { ll xx,yy; for(ll i=0;i<4;i++) { xx=x+dir[i][0]; yy=y+dir[i][1]; if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&mp[xx][yy]!='#') { s++; mp[xx][yy]='#'; dfs(xx,yy); } } } int main() { while(~scanf("%lld %lld",&m,&n)&&m&&n) { ll xx,yy; for(ll i=1;i<=n;i++) { for(ll j=1;j<=m;j++) { scanf(" %c",&mp[i][j]); if(mp[i][j]=='@') { xx=i; yy=j; } } } s=1; mp[xx][yy]='#'; dfs(xx,yy); cout<<s<<endl; } }
P1162 填涂顏色
建議從1開始讀入，因?yàn)檫@樣有一個好處，能夠建立起天然的下標(biāo)為0的圍墻數(shù)組，可以防止數(shù)組下標(biāo)小于0，以至于越界
dfs1
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn=1e6+10; ll n; ll mp[35][35]; ll vis[35][35]; ll dir[4][2]= { {-1,0},{1,0},{0,-1},{0,1} }; void dfs(ll x,ll y) { if(x==0||y==0||x>n||y>n) return; for(ll i=0; i<4; i++) { ll xx=x+dir[i][0],yy=y+dir[i][1]; if(mp[xx][yy]!=1&&xx>=1&&xx<=n&&yy>=1&&yy<=n&&!vis[xx][yy]) { vis[xx][yy]=1; dfs(xx,yy); } } } int main() { memset(vis,0,sizeof vis); memset(mp,0,sizeof mp); scanf("%lld",&n); for(ll i=1; i<=n; i++) { for(ll j=1; j<=n; j++) { cin>>mp[i][j]; } } for(ll i=1;i<=n;i++) { if(mp[1][i]==0) dfs(1,i); if(mp[i][1]==0) dfs(i,1); if(mp[n][i]==0) dfs(n,i); if(mp[i][n]==0) dfs(i,n); } for(ll i=1; i<=n; i++) { for(ll j=1; j<=n; j++) { if(j>1) cout<<' '; if(mp[i][j]!=1&&!vis[i][j]) mp[i][j]=2; cout<<mp[i][j]; } cout<<endl; } }
dfs2
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll mp[35][35]; ll n; ll dir[4][2]={ {-1,0},{1,0},{0,-1},{0,1} }; void dfs(ll x,ll y) { mp[x][y]=3; for(ll i=0;i<4;i++) { ll xx=x+dir[i][0],yy=y+dir[i][1]; if(xx>=0&&yy>=0&&xx<=n+1&&yy<=n+1&&mp[xx][yy]==0) { dfs(xx,yy); } } } int main() { scanf("%lld",&n); for(ll i=1;i<=n;i++) { for(ll j=1;j<=n;j++) { cin>>mp[i][j]; } } dfs(0,0); for(ll i=1;i<=n;i++) { for(ll j=1;j<=n;j++) { if(j>1) { cout<<' '; } if(mp[i][j]==3) { mp[i][j]=0; } else if(mp[i][j]==0) { mp[i][j]=2; } cout<<mp[i][j]; } cout<<endl; } }
ganmao病毒被消滅
關(guān)鍵代碼就兩行，還有一個暗坑
關(guān)鍵代碼：
if(sum+a[xx][yy]>=dp[xx][yy]||xx<1||yy<1||xx>n||yy>n||vis[xx][yy]||!a[xx][yy])continue; dp[xx][yy]=sum+a[xx][yy];
當(dāng)你已經(jīng)找到一條較小的路徑之后，那么從上一個點(diǎn)出發(fā)，其他路徑都沒有必要再將較大的路徑賦值給這條較小的路徑，可以直接continue。
暗坑：
如果被一排或者一行的0擋住那么輸出0，最好的方法就是定義一個全局的flag標(biāo)記，如果flag等于1則表示有結(jié)果，否則輸出0。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll inf=0x3f3f3f3f; ll a[105][105]; ll dir[4][2]= { {-1,0},{1,0},{0,-1},{0,1} }; bool vis[105][105]= {0}; ll dp[105][105]; ll s=inf; ll n; ll flag=0; void dfs(ll x,ll y,ll sum) { if(x==n&&y==n) { s=min(s,sum); flag=1; return; } for(ll i=0; i<4; i++) { ll xx=x+dir[i][0],yy=y+dir[i][1]; if(sum+a[xx][yy]>=dp[xx][yy]||xx<1||yy<1||xx>n||yy>n||vis[xx][yy]||!a[xx][yy])continue; dp[xx][yy]=sum+a[xx][yy]; vis[xx][yy]=1; dfs(xx,yy,sum+a[xx][yy]); vis[xx][yy]=0; } } int main() { scanf("%lld",&n); for(ll i=1; i<=n; i++) { for(ll j=1; j<=n; j++) { scanf("%lld",&a[i][j]); } } memset(vis,0,sizeof vis); memset(dp,inf,sizeof dp); vis[1][1]=1; dp[1][1]=a[1][1]; dfs(1,1,a[1][1]); if(flag) printf("%lld\n",s); else printf("0\n"); return 0; }
最小路徑和
核心代碼仍然是上題的兩行，且無暗坑，且僅有兩個方向:右和下，代碼就別到leetcode上交了，主要是為了學(xué)習(xí)dfs那兩行核心代碼的作用
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn=1e3+10; const ll inf=0x3f3f3f3f; ll m,n; ll mp[maxn][maxn],vis[maxn][maxn]; ll s=inf; ll dp[maxn][maxn]; ll dir[2][2]={ {1,0},{0,1} }; void dfs(ll x,ll y,ll sum) { if(x==m&&y==n) { s=min(s,sum); return; } for(ll i=0;i<2;i++) { ll xx=x+dir[i][0],yy=y+dir[i][1]; if(xx<1||yy<1||xx>m||yy>n||sum+mp[xx][yy]>=dp[xx][yy])continue; dp[xx][yy]=sum+mp[xx][yy]; vis[xx][yy]=1; dfs(xx,yy,sum+mp[xx][yy]); vis[xx][yy]=0; } } int main() { scanf("%lld%lld",&m,&n); for(ll i=1;i<=n;i++) { for(ll j=1;j<=m;j++) { scanf("%lld",&mp[i][j]); } } memset(vis,0,sizeof vis); memset(dp,inf,sizeof dp); vis[1][1]=1; dp[1][1]=mp[1][1]; dfs(1,1,mp[1][1]); printf("%lld\n",s); }
P1451 求細(xì)胞數(shù)量（連通塊個數(shù)）
數(shù)字1-9表示存在細(xì)胞，把當(dāng)前位置賦值為0，默認(rèn)視作不存在細(xì)胞，本次搜索完之后，無需將原先位置的數(shù)還原。
#include <bits/stdc++.h> #define sc2(a,b) scanf("%lld%lld", &a,&b) #define mem(a) memset(a,false,sizeof a) using namespace std; typedef long long ll; ll n,m; ll s=0; ll a[105][105]; ll dir[4][2]={ {-1,0},{1,0},{0,1},{0,-1} }; void dfs(ll x,ll y) { if(x<=0||y<=0||x>n||y>m)return; a[x][y]=0; for(ll i=0;i<4;i++) { ll xx=x+dir[i][0],yy=y+dir[i][1]; if(a[xx][yy]) { dfs(xx,yy); } } } int main() { sc2(n,m); s=0; mem(a); mem(vis); for(ll i=1;i<=n;i++) { for(ll j=1;j<=m;j++) { scanf("%1lld",&a[i][j]); } } for(ll i=1;i<=n;i++) { for(ll j=1;j<=m;j++) { if(a[i][j]) s++, dfs(i,j); } } printf("%lld\n",s); }
-------------------------------------------------------------------------------------------------------------
作者：Drophair
本文版權(quán)歸作者和博客園共有，歡迎轉(zhuǎn)載，但未經(jīng)作者同意必須在文章頁面給出原文連接，否則保留追究法律責(zé)任的權(quán)利。
浙公網(wǎng)安備 33010602011771號