北京商务网站建设,湛江网站建设技术托管,wordpress开启redis缓存,网站建设和管理颁奖dfs的搜索是基于栈#xff0c;但一般可以用用递归实现#xff0c;实际上用的是系统栈。有内部搜索和外部搜索两种#xff0c;内部搜索是在图的内部#xff0c;内部搜索一般基于连通性#xff0c;从一个点转移到另一个点#xff0c;或者判断是否连通之类的问题#xff0c…dfs的搜索是基于栈但一般可以用用递归实现实际上用的是系统栈。有内部搜索和外部搜索两种内部搜索是在图的内部内部搜索一般基于连通性从一个点转移到另一个点或者判断是否连通之类的问题只需要标记避免重复访问即可不需要还原状态而外部搜索则是将一张图视为一种状态每一个状态延伸得到新的状态要保证每个状态往外延伸时都是相同的那么就需要还原状态。
搜索顺序也很重要我们要找到合适的搜索顺序保证不漏的搜出每一种情况重复当然没什么问题。
另外同宽搜相比深搜的代码会简单一些但是却有爆栈的风险递归层数比较高的时候需要注意。
1112. 迷宫活动 - AcWing 思路本质上就是判断能不能从这点到达另一点那么就是连通性问题深搜宽搜都可以这里我们用深搜来实现。
#includebits/stdc.h
using namespace std;
int n;
char s[120][120];
int sx,sy,ex,ey;
int dx[]{0,0,1,-1};
int dy[]{1,-1,0,0};
int st[120][120];
int dfs(int x,int y)
{if(s[x][y]#) return 0; if(xexyey) return 1;st[x][y]1;for(int i0;i4;i){int nxxdx[i],nyydy[i];if(nx0||nxn||ny0||nyn) continue;if(st[nx][ny]) continue;if(dfs(nx,ny)) return 1;}return 0;
}
int main()
{int t;scanf(%d,t);while(t--){scanf(%d,n);for(int i0;in;i) scanf(%s,s[i]);scanf(%d%d%d%d,sx,sy,ex,ey);if(dfs(sx,sy)) coutYESendl;else coutNOendl;memset(st,0,sizeof st);}
}
1113. 红与黑(1113. 红与黑 - AcWing题库) 思路实际上就是统计一个连通块内有多少个元素。
#includebits/stdc.h
using namespace std;
char g[30][30];
int n,m;
int cnt;
int dx[]{0,0,1,-1};
int dy[]{1,-1,0,0};
int st[30][30];
void dfs(int x,int y)
{st[x][y]1;cnt;for(int i0;i4;i){int nxxdx[i],nyydy[i];if(nx0||nxn||ny0||nym) continue;if(st[nx][ny])continue;if(g[nx][ny]#) continue;dfs(nx,ny);}
}
int main()
{while(scanf(%d%d,m,n)){if(!n!m) break;for(int i0;in;i) scanf(%s,g[i]);for(int i0;in;i)for(int j0;jm;j)if(g[i][j]){cnt0;dfs(i,j);coutcntendl;break;}memset(st,0,sizeof st);}
} 1116. 马走日(活动 - AcWing) 思路这题看似是说在棋盘内部移动但实际上每次统计一个结果的前提是整个棋盘都被遍历而且每一步移动有八个选择理想情况八个选择各自代表不同的状态所以我们需要还原状态只用在最后递归到所有节点都访问过时记录一下即可。
#includebits/stdc.h
using namespace std;
int n,m;
int st[10][10];
int ans;
int dx[]{1,1,-1,-1,2,2,-2,-2};
int dy[]{2,-2,2,-2,1,-1,1,-1};
void dfs(int x,int y,int k)
{if(kn*m) {ans;return;}st[x][y]1;for(int i0;i8;i){int nxxdx[i],nyydy[i];if(nx0||nxn||ny0||nym) continue;if(st[nx][ny]) continue;dfs(nx,ny,k1);}st[x][y]0;
}
int main()
{int t;scanf(%d,t);while(t--){int x,y;scanf(%d%d%d%d,n,m,x,y);ans0;dfs(x,y,1);coutansendl;}
}ps:特殊情况单独判返回的时候一定要注意状态有没有请干净。
1117. 单词接龙活动 - AcWing 思路这里首先要想搜索我们需要建立单词与单词之间的关系准确来说我们需要知道哪些单词可以接在哪些单词的后面它们的重合长度是多少这里的重合长度一定要越小越好因为我们可以任意选择重合长度。
那么预处理完之后直接深搜记录最大值即可。
另外要注意每个单词只能用两次那么需要记录一下当前单词已经用了几次了我们可以用下标来实现。
#includebits/stdc.h
using namespace std;
int n;
string s[30];
int used[30];
int g[30][30];
int mx;
void dfs(string r,int k)
{if(used[k]2) return;used[k];for(int i0;in;i){if(g[k][i]used[i]2){string tmprs[i].substr(g[k][i]);//coutr s[i].substr(g[k][i]) g[k][i]endl;mxmax(mx,(int)tmp.size());dfs(rs[i].substr(g[k][i]),i);}}used[k]--;
}
int main()
{scanf(%d,n);for(int i0;in;i) cins[i];for(int i0;in;i){for(int j0;jn;j){for(int k1;kmin(s[i].size(),s[j].size());k){if(s[i].substr(s[i].size()-k,k)s[j].substr(0,k)){g[i][j]k;break;}}//printf(%d ,g[i][j]);}//printf(\n);}char c;cinc;mx0;for(int i0;in;i){if(s[i][0]c){mxmax(mx,(int)s[i].size());dfs(s[i],i);}}coutmx;
} 1118. 分成互质组(活动 - AcWing) 思路如果我们将第一个数放在第一组那么遍历后面的数如果不与第一组中的数互质那么就可以放进这一组否则就只能新开一组如此递归来实现就可保证将所有的数都分好组同时是分组最少的。
另外由于放进同一个组内的顺序无所谓所以当不用新开一个组的时候遍历下一层的时候直接从后一个元素开始遍历否则如果新开组那么就要从开头开始遍历。因为是按顺序遍历的所以当前元素被遍历前它之前的元素与这一组的关系都已经判断过了所以如果不新开组那么就没必要再往前看。
#includebits/stdc.h
using namespace std;
int n;
int a[20];
int g[20][20];
int ans10;
int st[20];
int gcd(int a,int b)
{return b?gcd(b,a%b):a;
}
int check(int u,int g[],int cn)
{for(int i0;icn;i){if(gcd(a[u],a[g[i]])1) return 0; }return 1;
}
void dfs(int u,int c,int k,int cn)//u是此时从哪个点开始判断c是当前处在第几个组k是已经分配几个点了,cn当前组中有多少个元素
{if(cans) return;if(kn){ans min(ans,c);return;}int flag1;for(int iu;in;i){if(!st[i]check(i,g[c],cn))//一个点都不能放入了再新开{st[i]1;g[c][cn]i;dfs(u1,c,k1,cn1);st[i]0;flag0;}}if(flag) dfs(0,c1,k,0);
}
int main()
{scanf(%d,n);for(int i0;in;i) scanf(%d,a[i]);dfs(0,1,0,0);coutans;
}
