题意
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
解法：n皇后的变形，注意放的位置不一定，并不是每一行都要放，计个step，然后dfs每一个点时，记得回溯上去处理一下，把vis[i]置为0，step--即可，然后处理完此次结束后，dfs（x+1),处理下一位；
#include<cstdio> #include<cstring> using namespace std; #define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++) #define per(i,j,k) for(int i=(int)k;i>=(int)j;i--) int step,ans,n,k; char mp[20][20]; bool vis[20]; void dfs(int x){ if(step==k){ ans++; return ; } if(x>=n)return ; for(int i=0;i<n;i++){ if(!vis[i]&&mp[x][i]==‘#‘){ step++; vis[i]=1; dfs(x+1); vis[i]=0; step--; } } dfs(x+1); } int main(){ while(~scanf("%d %d",&n,&k)){ memset(vis,0,sizeof vis); if(n+k<0)break; rep(i,0,n-1){ scanf("%s",mp[i]); } ans=step=0; dfs(0); printf("%d\n",ans); } return 0; }
题意:就是个三维迷宫，直接广搜即可，用一个方向数组
#include<cstdio> #include<queue> #include<cstring> using namespace std; #define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++) #define per(i,j,k) for(int i=(int)k;i>=(int)j;i--) #define pb push_back #define fi first #define se second typedef long long ll; typedef unsigned long long ull; typedef long double ldb; char map[50][50][50]; bool vis[50][50][50]; struct point {int x,y,z,step;}; int L,R,C,ans,sx,sy,sz,ex,ey,ez; int dir[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}}; bool check(point p){ if(p.x>=L||p.y>=R||p.z>=C||p.x<0||p.y<0||p.z<0||vis[p.x][p.y][p.z]==1||map[p.x][p.y][p.z]==‘#‘) return 0; return 1; } void bfs(){ point tmp; tmp.x=sx,tmp.y=sy,tmp.z=sz,vis[tmp.x][tmp.y][tmp.z]=1,tmp.step=0; queue<point>Q; Q.push(tmp); while(!Q.empty()){ tmp=Q.front(); Q.pop(); if(tmp.x==ex&&tmp.y==ey&&tmp.z==ez){ ans=tmp.step; return ; } for(int i=0;i<6;i++){ point next; next.x=tmp.x+dir[i][0]; next.y=tmp.y+dir[i][1]; next.z=tmp.z+dir[i][2]; if(check(next)){ vis[next.x][next.y][next.z]=1; next.step=tmp.step+1; Q.push(next); } } } return ; } int main(){ while(~scanf("%d%d%d",&L,&R,&C),L+R+C){ memset(vis,false,sizeof vis); // memset(step,0,sizeof step); for(int i=0;i<L;i++){ for(int j=0;j<R;j++){ scanf("%s",map[i][j]); for(int k=0;k<C;k++){ if(map[i][j][k]==‘S‘){ sx=i,sy=j,sz=k; } else if(map[i][j][k]==‘E‘){ ex=i,ey=j,ez=k; } } } } ans=0; bfs(); if(!ans)printf("Trapped!\n"); else printf("Escaped in %d minute(s).\n",ans); } return 0; }
题意：给你n和m，问几步能走到，直接广搜即可
#include<cstdio> #include<queue> #include<cstring> using namespace std; #define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++) #define per(i,j,k) for(int i=(int)k;i>=(int)j;i--) #define pb push_back #define fi first #define se second #define check(x) (x<=N&&x>=0) typedef long long ll; typedef unsigned long long ull; typedef long double ldb; const int N=1e5+5; bool vis[N]; int step[N]; int n,k; void bfs(){ queue<int>Q; vis[n]=1; step[n]=0; Q.push(n); while(!Q.empty()){ int s=Q.front(); if(s==k)return ; Q.pop(); if(check(s+1)&&!vis[s+1]){ vis[s+1]=1; step[s+1]=step[s]+1; Q.push(s+1); } if(check(s-1)&&!vis[s-1]){ vis[s-1]=1; step[s-1]=step[s]+1; Q.push(s-1); } if(check(s<<1)&&!vis[s<<1]){ vis[s<<1]=1; step[s<<1]=step[s]+1; Q.push(s<<1); } } } int main(){ while(~scanf("%d%d",&n,&k)){ if(n>=k){ printf("%d\n",n-k); } else { memset(vis,false,sizeof vis); memset(step,0,sizeof step); bfs(); printf("%d\n",step[k]); } } return 0; }
题意： 给你一个01网格图，问你怎么按这些点，使得网格图全部置为0，找出字典序最小的方案；
解法： 这题用到二进制思想，解法就是枚举第一行的按键，然后剩下的每一行都可以由上一行递推而来；
递推公式为：press[i][j]=(mp[i-1][j]+press[i-1][j]+press[i-1][j+1]+press[i-2][j]+press[i-1][j-1])&1;
最后判断一下情况是否符合，即最后一行按键是否能全部熄灭，
这里我犯了一个错误，就是判断最后一行时没有按照递推公式算导致错误；
然后枚举第一行的按键用到了二进制，即枚举0<i<(1<<m)，表示有m位二进制数，然后用位运算截取每一位数，即为 press[1][j]=(i>>(m-j))&1;
over
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; int mp[20][20],ans[20][20],press[20][20]; int n,m; const int inf=0x3f3f3f3f; int guess(){ for(int i=2;i<=n;i++){ for(int j=1;j<=m;j++){ press[i][j]=(mp[i-1][j]+press[i-1][j]+press[i-1][j+1]+press[i-2][j]+press[i-1][j-1])&1; } } for(int j=1;j<=m;j++){ if((press[n][j]+mp[n][j]+ press[n-1][j]+press[n][j-1]+press[n][j+1])&1!=0) return inf; } int cnt=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cnt+=press[i][j]; } } return cnt; } int main(){ while(~scanf("%d%d",&n,&m)){ memset(mp,0,sizeof mp); memset(ans,0,sizeof ans); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&mp[i][j]); int res=inf; for(int i=0;i<(1<<m);i++){ memset(press,0,sizeof press); int test=1; for(int j=1;j<=m;j++){ press[1][j]=(i>>(m-j))&1; } // cout<<"test:"<<i<<" "<<guess()<<endl; // for(int i=1;i<=n;i++) // for(int j=1;j<=m;j++) // printf("%d%c",press[i][j],j==m?‘\n‘:‘ ‘); int sum=guess(); if(res>sum){ res=sum; memcpy(ans,press,sizeof press); } } if(res==inf)printf("IMPOSSIBLE\n"); else { // cout<<"test:"<<endl; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) printf("%d%c",ans[i][j],j==m?‘\n‘:‘ ‘); } } return 0; }
PS：还是太菜了，要坚持刷题，写博客；
原文：https://www.cnblogs.com/littlerita/p/12305990.html
