深度搜索--简单的背包问题
- 就是从基础开始，每次做出选择，根据选择变更函数值
#include<stdio.h> int V,C; int num,weight,ans=0; int w[100]; int p[100]; void DFS(int index, int tempweight, int tempprice){ if(index==num) return; if((tempweight+w[index])<=weight){ if((tempprice+p[index])>ans) ans=tempprice+p[index]; DFS(index+1,tempweight+w[index],tempprice+p[index]); } DFS(index+1,tempweight,tempprice); } int main(){ scanf("%d %d",&num,&weight); ans=0; for(int i=0;i<num;i++) scanf("%d",&w[i]); for(int i=0;i<num;i++) scanf("%d",&p[i]); DFS(0,0,0); printf("%d ",ans); return 0; }
全排列
- 这个DFS结果需要存储，并且在当前分支不可访问，那么在退出这个分支进入其他分支的时候是可访问的，所以要在DFS下一层后面修改为可访问。（因为那个函数结束的时候就说明那个分支的延续结束了）
- 这里使用的数组，直接覆盖到相同位置就可以，要是使用vector，当前分支结束，要把存的这个点删掉
#include<stdio.h> #include<string.h> int num; int ans[100]; int pd[100]; void DFS(int x){ if(x==num){ for(int i=0;i<num;i++) printf("%5d",ans[i]); printf(" "); return; } for(int i=1;i<=num;i++){ if(pd[i]==false){ pd[i]=true; ans[x]=i; DFS(x+1); pd[i]=false; } } } int main(){ memset(pd,0,sizeof(pd)); scanf("%d",&num); DFS(0); return 0; }
简单广搜BFS--地图中几个块
- 注意一下外面代表方向的数组不要和函数里面变量重复了，第一次不小心数组和变量都用的x
- 每一个开始访问的点让ans+1，然后进入BFS，不是在BFS里面选不同的起始点，BFS只负责把一个点扩展完
- 入队的标0，避免重复进队（就是在第一次扩展遇到这个点，也就是刚入队就标0，不能等到从队列拿出来标，那样可能会导致反复入队）
#include<stdio.h> #include<queue> using namespace std; struct node{ int x; int y; }a[100]; int mp[100][100]; int ans=0,m,n; int mpx[4]={-1,0,0,1}; int mpy[4]={0,-1,1,0}; queue<node>q; bool pd(int x,int y){ if(x>=0 && x<m && y>=0 && y<n && mp[x][y]==1){ mp[x][y]=0; return true; } return false; } void BFS(int x, int y){ ans++; node temp,temp1; temp.x=x; temp.y=y; q.push(temp); while(!q.empty()){ temp=q.front(); q.pop(); for(int i=0;i<=3;i++){ int tempx=temp.x+mpx[i]; int tempy=temp.y+mpy[i]; if(pd(tempx,tempy)){ temp1.x=tempx; temp1.y=tempy; q.push(temp1); } } } } int main(){ scanf("%d %d",&m,&n); for(int i=0;i<m;i++) { for(int j=0;j<n;j++) scanf("%d",&mp[i][j]); } for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(mp[i][j]==1){ mp[i][j]=0; BFS(i,j); } } } printf("%d",ans); return 0; }
BFS--走迷宫
- 结构体要带step，一个循环内的都是当前node的step+1。（入队之前修改，因为入队以后存的是副本，不会存到点本身，当然这道题里面没影响的）
- 可行的进队列，最后找到符合条件的位置退出循环。
- 注意把这个点进队列的时候就要标记成不可再访问，避免循环，当这个点成为front被访问时候，要记得让他出队
#include<stdio.h> #include<queue> using namespace std; int n,m; int startx,starty,endx,endy; int ans=0; char mp[100][100]; int mpx[4]={0,0,1,-1}; int mpy[4]={1,-1,0,0}; int pd(int x,int y){ if(x>=0 && x<n && y>=0 && y<m){ if(mp[x][y]=='*') return 0; if(mp[x][y]=='.'){ mp[x][y]='*'; return 1; } if(mp[x][y]=='T') return 2; } return 0; } struct node{ int x; int y; int step; }; queue<node>q; void BFS(int x,int y){ node temp,temp1; temp.x=x; temp.y=y; temp.step=0; q.push(temp); while(!q.empty()){ temp=q.front(); q.pop(); int nowx=temp.x; int nowy=temp.y; for(int i=0;i<=3;i++){ int tempx=nowx+mpx[i]; int tempy=nowy+mpy[i]; int tempnum=pd(tempx,tempy); if(tempnum==2){ ans=temp.step+1; return; } else if(tempnum==1){ temp1.step=temp.step+1; temp1.x=tempx; temp1.y=tempy; q.push(temp1); } } } } int main(){ scanf("%d%d",&n,&m); scanf("%d%d",startx,starty); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ scanf("%c",&mp[i][j]); if(mp[i][j]=='S'){ startx=i; starty=j; } else if(mp[i][j]=='T'){ endx=i; endy=j; } } getchar(); } BFS(startx,starty); printf("%d ",ans); return 0; }
如果队列中的元素在入队吼还需要修改，那么入队最好存下标，不要存某个元素