1 连通性问题（内部搜索）
内部搜索一般不用恢复现场
1.迷宫
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=110; char g[N][N]; int sx,sy,ex,ey; int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; bool st[N][N]; int n; bool dfs(int x,int y) { if(g[x][y]=='#') return false;//假如是障碍 if(x==ex&&y==ey) return true;//假如是终点了 st[x][y]=true;//标记这个点走过 for(int i=0;i<4;i++)//枚举四个方向 { int a=x+dx[i],b=y+dy[i]; if(a<0||a>=n||b<0||b>=n) continue;//越界 if(st[a][b]) continue;//走过 if(dfs(a,b)) return true;//假如后面能走到 } return false;//反之走不到 } int main() { int T; cin>>T; while(T--) { cin>>n; memset(st,0,sizeof st);//清空上一层状态 for(int i=0;i<n;i++) cin>>g[i]; cin>>sx>>sy>>ex>>ey; if(dfs(sx,sy)) puts("YES");//假如能走到 else puts("NO"); } return 0; }
2.红与黑
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=25; int n,m,cnt; char g[N][N]; int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; bool st[N][N]; void dfs(int x,int y) { st[x][y]=true;//标记走过 for(int i=0;i<4;i++) { int a=x+dx[i],b=y+dy[i]; if(a<0||a>=n||b<0||b>=m) continue;//越界 if(st[a][b]||g[a][b]!='.') continue;//假如走过或者不能走的 cnt++;//连通数增加 dfs(a,b); } } int main() { while(cin>>m>>n,n||m) { memset(st,0,sizeof st);//清空上一层状态 for(int i=0;i<n;i++) cin>>g[i]; int x,y; for(int i=0;i<n;i++)//找起点 for(int j=0;j<m;j++) if(g[i][j]=='@') { x=i,y=j; break; } cnt=1;//自己起点是一个点 dfs(x,y);//找一下联通多少个 cout<<cnt<<endl;//输出个数 } return 0; }
2.搜索顺序（外部搜索）
外部搜索一般要恢复现场
1.马走日
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=15; int n,m,sx,sy,cnt=1,ans; bool st[N][N]; int dx[8]={-2,-1,1,2,2,1,-1,-2},dy[8]={1,2,2,1,-1,-2,-2,-1}; void dfs(int x,int y) { if(cnt==n*m)//假如走完所有点 { ans++;//方案加1 return; } st[x][y]=true;//标记这个点走过 for(int i=0;i<8;i++)//枚举八个方向 { int a=x+dx[i],b=y+dy[i]; if(a<0||a>=n||b<0||b>=m) continue;//越界 if(st[a][b]) continue;//走过 cnt++;//步数+1 dfs(a,b); cnt--;//恢复现场步数-1 } st[x][y]=false;//恢复现场 } int main() { int T; cin>>T; while(T--) { ans=0; cin>>n>>m>>sx>>sy; dfs(sx,sy); cout<<ans<<endl; } return 0; }
2.单词接龙
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=25; string word[N]; int g[N][N],ans=0; int used[N]; int n; void dfs(string dragon,int u) { ans=max(ans,(int)dragon.size());//取一次龙的最长度 used[u]++;//该位置使用加1 for(int i=0;i<n;i++) if(g[u][i]&&used[i]<2)//枚举看看能不能接到该字符串后面 dfs(dragon+word[i].substr(g[u][i]),i); used[u]--;//恢复现场 } int main() { cin>>n; for(int i=0;i<n;i++) cin>>word[i]; char start;//龙的开头 cin>>start; for(int i=0;i<n;i++)//用来判断那两个可以接到一起 for(int j=0;j<n;j++) { string a1=word[i],a2=word[j]; for(int k=1;k<min(a1.size(),a2.size());k++)//从小开始搜看能不能接，接的越少龙越长 if(a1.substr(a1.size()-k,k)==a2.substr(0,k)) { g[i][j]=k; break; } } for(int i=0;i<n;i++) if(word[i][0]==start)//假如符合龙的开头 dfs(word[i],i); cout<<ans<<endl; return 0; }
3.分成互质组
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=15; int p[N],n,ans=10; bool st[N]; int group[N][N]; int gcd(int a,int b)//用来求最小公倍数，假如最小公倍数大于1说明不互质，反之互质 { return b?gcd(b,a%b):a; } bool check(int g[],int gc,int u) { for(int i=0;i<gc;i++)//判断该组的所有元素是否与该元素互质 if(gcd(p[g[i]],p[u])>1)//假如不互质 return false; return true;//反之互质 } void dfs(int g,int gc,int cnt,int start)//表示有多少组，该组有多少个元素，已用元素个数，已经用到第几个元素 { if(g>=ans) return;//假如组数已经大于ans，则没必要更新了 if(cnt==n) ans=g;//g已经是最小值了，假如大于ans已经在上一步弹掉了 int flag=true;//用来标记是否需要新开一组 for(int i=start;i<n;i++)//找后面的元素是否能假如该组 if(!st[i]&&check(group[g],gc,i))//假如可以加 { st[i]=true;//标记该元素已经用过了 group[g][gc]=i;//该组第gc的元素就是他 dfs(g,gc+1,cnt+1,i+1);//下一步是组数不变，元素加1，已用元素加1，从下一个元素开始 st[i]=false;//恢复现场 flag=false;//说明不用新开组 } if(flag) dfs(g+1,0,cnt,0);//假如新开组，则组数加1，元素0个，已用cnt个，下标从0开始，因为该组是没有元素的 } int main() { cin>>n; for(int i=0;i<n;i++) cin>>p[i]; dfs(1,0,0,0);//从一组开始，该组的元素0个，已用元素0个，元素从0开始 cout<<ans<<endl; return 0; }
