好奇怪的游戏（bfs
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int x1,x2,y1,y2;
queue<int>qx;
queue<int>qy;
int xx[15] ={1,1,2,2,-1,-1,-2,-2,2,2,-2,-2};
int yy[15] ={2,-2,1,-1,2,-2,-1,1,2,-2,-2,2};
int dis[120][120];
int main()
{
int T = 2;
while(T--)
{
scanf("%d%d",&x1,&y1);
while(!qx.empty()) qx.pop();
while(!qy.empty()) qy.pop();
memset(dis,0,sizeof(dis));
qx.push(x1);
qy.push(y1);
dis[x1][y1] = 0;
while(!qx.empty())
{
int x = qx.front();
int y = qy.front();
qx.pop();
qy.pop();
if(x == 1 && y == 1)
{
printf("%d\n",dis[1][1]);
break;
}
for(int i=0;i<12;i++)
{
int tx = x + xx[i];
int ty = y + yy[i];
if(tx>=1 && tx <= 50 && ty >= 1 && ty <= 50 && dis[tx][ty] == 0)
{
dis[tx][ty] = dis[x][y] + 1;
qx.push(tx);
qy.push(ty);
}
}
}
}
return 0;
}
思路：（来自题解。。。
完全背包固然是正解，但万一比赛时我们脑子瓦特想不出正解怎么办呢？
那就是我们的爆搜出场的时候了！（滑稽）
但是纯爆搜显然是不行的，m<=100000，这个数据范围很有可能得不了高分甚至爆0，所以我们就要进行一些优化。
首先是剪枝。我们可以用 ans 存下当前的最好答案，如果在搜索时当前选的数的数量已经大于ans了，那肯定就没必要找了，这样是白费力气。另外，1^4+2^4和2^4+1^4是一样的，我们用一个last让选出的数列变成升序，同样可以减少时间消耗。
另外搜的顺序非常重要。如果我们从1往上搜，那第一个选出来的肯定是全1的序列。这种情况我们肯定不想要，希望直接将其剪枝。那么怎么操作呢？结合刚才说的，我们可以确定一个娇小较小的ans，然后之后的搜索肯定不会超过这个步数。没错，从最大往小的搜可以很好地完成这个任务。如果不这样的话只会有30分。
#include<bits/stdc++.h>
using namespace std;
int n;
int ans=999999;
void dfs(int tot,int k,int last)
{
if(k>ans) return;
if(tot>n) return;
if(tot==n)
{
if(ans>k) ans=k;
return;
}
int i;
for(i=last;i*i*i*i<=n-tot;) i++;
for(;i>=last;i--)
dfs(tot+i*i*i*i,k+1,i);
}
int main()
{
cin>>n;
dfs(0,0,1);
cout<<ans;
return 0;
}
江湖数（dfs
#include<iostream>
#include<cstdio>
using namespace std;
char a[120][120];
bool vis[120][120];
int n,m;
int xx[8] = {0,0,1,1,1,-1,-1,-1};
int yy[8] = {1,-1,1,0,-1,1,0,-1};
void dfs(int x,int y)
{
for(int i=0;i<8;i++)
{
int tx = x + xx[i];
int ty = y + yy[i];
if(!vis[tx][ty] && a[tx][ty] == 'W' && tx >=1 && tx <= n && ty >=1 && ty <= m)
{
vis[tx][ty] = 1;
dfs(tx,ty);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
int ans = 0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j] == 'W' && !vis[i][j])
{
dfs(i,j);
ans ++;
}
}
}
printf("%d\n",ans);
return 0;
}
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int ans=0,n,k,x,a[21],num=0;
bool p(int q)
{
int i;
if(q==2) return true;
for(i=2;i*i<=q;i++)
{
if(q%i==0) return false;
}
return true;
}
void dfs(int x,int y)//定义深搜的函数，y是当前最后选过的数在数组中的位置，x是当前正在选择第几个数，和用num变量储存
{
int i,j;
if(x > k){//如果选的数已经比k多了，就检测总和num是否为质数
if(p(num)) ans++; //是就增加ans
return ;
}
for(i=y+1;i<=n;i++)//否则继续搜索下一个数
{
num+=a[i];//取数
dfs(x+1,i);//搜索
num-=a[i];//回溯
}
}
int main()
{
int i,j;
scanf("%d%d",&n,&k);//输入，不解释
for(i=1;i<=n;i++) scanf("%d",&a[i]);
dfs(1,0);//开始深搜，选择第一个数，由于没有选过任意一个数，y=0
printf("%d",ans);//输出答案
return 0;
}
字符串（bfs
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,ans;
void dfs(int now,int s,int l) // now 表示0 or 1 s 表示相邻的个数 l 判断是否结束
{
if(l == n)
{
ans ++;
return ;
}
if(s<2) dfs(now,s+1,l+1);
dfs(now^1,1,l+1);
}
int main()
{
scanf("%d",&n);
if(n == 0)
ans = 0;
else
dfs(0,1,1),dfs(1,1,1);
printf("%d\n",ans);
return 0;
}
去看电影（dfs
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[20];
bool vis[20];
int n,m,maxx=-1;
void dfs(int k,int ans)
{
for(int i=k;i<=m;i++)
{
if(!vis[i])
{
vis[i] = 1;
ans += a[i];
if(ans <= n)
{
maxx = max(ans,maxx);
dfs(i+1,ans);
}
vis[i] = 0;
ans -= a[i];
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&a[i]);
}
dfs(1,0);
cout<<maxx<<endl;
return 0;
}
传球（ 搜索 40分。。。
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,ans = 0;
queue<int>q1,q2;
void bfs()
{
while(!q1.empty())
{
int now = q1.front();
q1.pop();
int step = q2.front();
q2.pop();
if(step > m)
return ;
step ++;
int ne = now +1;
if(ne == n +1)
ne = 1;
if(ne == n && step == m)
ans ++;
q1.push(ne);
q2.push(step);
int nne = now -1;
if(nne == 0)
nne = n;
if(nne == n && step == m)
ans ++;
q1.push(nne);
q2.push(step);
}
}
int main()
{
scanf("%d%d",&n,&m);
q1.push(n);
q2.push(0);
bfs();
cout<<ans<<endl;
}
约瑟夫问题（搜索
#include<iostream>
#include<cstdio>
#include<queue>
#include<map>
using namespace std;
int a[120];
int n,m;
queue<int>q;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
q.push(i);
}
if(n == 0)
return 0;
while(!q.empty())
{
for(int i=1;i<=m-1;i++)
{
int a = q.front();
q.pop();
q.push(a);
}
cout<<q.front()<<" ";
q.pop();
}
return 0;
}
超级书架2（dfs
#include<iostream>
#include<cstdio>
using namespace std;
int a[120];
bool vis[120];
int n,m;
int ans = 1e9;
void dfs(int sum)
{
if(sum >= m)
{
ans = min(sum,ans);
return ;
}
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
vis[i] = 1;
dfs(sum + a[i]);
vis[i] = 0;
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
dfs(0);
cout<<ans - m<<endl;
return 0;
}
放苹果（递归
这道题其实就是一个分类讨论+递归，你可以选择有一个盘子一个苹果都不放，然后盘子数减1，或者（不可能两种方案都不选）每个盘子都放一个苹果，即苹果减去盘子的数量，就一直这样递归下去，就得到了最终的答案。注意：有0个苹果或1个盘子时，只有一种方案，所以（n==0||m==1）return 1，当n<0或m<1时，因为根本不存在这种情况，所以返回一个0
#include<iostream>
#include<cstdio>
using namespace std;
int T,n,m;
int solve(int n,int m)
{
if(n == 0 || m == 1)
return 1;
if(n<0||m<1)
return 0;
return solve(n,m-1) + solve(n-m,m);
}
int main()
{
cin>>T;
while(T--)
{
cin>>n>>m;
cout<<solve(n,m)<<endl;
}
return 0;
}
游戏（bfs
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
char a[2010][2010];
bool vis[2010][2010];
int dis[2010][2010];
int n,m;
int xx[4] = {0,0,1,-1};
int yy[4] = {1,-1,0,0};
queue<int>qx,qy;
int pd(int x,int y)
{
if( x>=1 && x<=n && y>=1&& y<=m && !vis[x][y] && a[x][y] != '#')
return 1;
return 0;
}
void bfs()
{
while(!qx.empty())
{
int x = qx.front();
int y = qy.front();
qx.pop();
qy.pop();
for(int i=0;i<4;i++)
{
int tx = x + xx[i];
int ty = y + yy[i];
if(pd(tx,ty))
{
qx.push(tx);
qy.push(ty);
vis[tx][ty] = 1;
dis[tx][ty] = dis[x][y] + 1;
}
}
}
}
int main()
{
int tx,ty,enx,eny;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
vis[i][j] = 0;
dis[i][j] = 1e9;
if(a[i][j] == 'm')
{
tx = i;
ty = j;
}
if(a[i][j] == 'd')
{
enx = i;
eny = j;
}
}
}
vis[tx][ty] = 1;
dis[tx][ty] = 0;
qx.push(tx);
qy.push(ty);
bfs();
if(dis[enx][eny] == 1e9)
cout<<"No Way!"<<endl;
else
cout<<dis[enx][eny]<<endl;
return 0;
}
海战（dfs
先预处理判断是否是不可行的情况，我们由题意可以知道，不可行的情况为两个船挨在了一起，即存在不是矩形的一个图案的情况。我们又可以知道，在一个 2*2 的矩形中，若在三个地方都是#，那么就一定存在不是矩形的情况，直接输出，Bad placement.
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int a[1010][1010];
bool vis[1010][1010];
int n,m;
int xx[4] = {0,0,1,-1};
int yy[4] = {1,-1,0,0};
int pd(int x,int y)
{
if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y] == 1 &&!vis[x][y])
return 1;
return 0;
}
void dfs(int x,int y)
{
vis[x][y] = 1;
a[x][y] = 0;
for(int i=0;i<4;i++)
{
int tx = x + xx[i];
int ty = y + yy[i];
if(pd(tx,ty))
{
dfs(tx,ty);
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
char ch;
cin>>ch;
if(ch == '.')
a[i][j] = 0;
else a[i][j] = 1;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
int sum = 0;
if(a[i][j]) sum ++;
if(a[i+1][j]) sum ++;
if(a[i][j+1]) sum ++;
if(a[i+1][j+1]) sum ++;
if(sum == 3)
{
cout<<"Bad placement."<<endl;
return 0;
}
}
}
int ans = 0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(!vis[i][j]&&a[i][j] == 1)
{
ans ++;
dfs(i,j);
}
}
}
printf("There are %d ships.\n",ans);
return 0;
}
简单的搜索，要求下一个大于等于上一个即可
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int a[15];
int n,m;
void print(int k)
{
for(int i=1;i<=k-1;i++)
{
cout<<a[i]<<"+";
}
cout<<a[k]<<endl;
}
void dfs(int s,int t)
{
if(s == 0)
{
print(t-1);
return ;
}
for(int i=1;i<=s;i++)
{
if(a[t-1] <= i && i < n)
{
a[t] = i;
s -= i;
dfs(s,t+1);
s += i;
}
}
}
int main()
{
cin>>n;
dfs(n,1);
return 0;
}
Catch That Cow（改错改了好久，**！
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int visit[100005] = {0};
int main()
{
int n,m;
while(scanf("%d%d",&n,&m) != EOF)
{
memset(visit,0,sizeof(visit));
queue<int> q;
q.push(n);
int t;
while(!q.empty())
{
t = q.front();
q.pop();
if(t == m)
{
break;
}
if(t > 0 && !visit[t-1])
{
visit[t-1] = visit[t]+1;
q.push(t-1);
}
if(t < m &&!visit[t+1])
{
visit[t+1] = visit[t]+1;
q.push(t+1);
}
if(t*2 < 100005 && !visit[t*2])
{
visit[2*t] = visit[t]+1;
q.push(2*t);
}
}
printf("%d\n",visit[m]);
}
return 0;
}
#include<iostream>
#include<queue>
using namespace std;
long long n;
queue<long long>q;
void bfs()
{
while(!q.empty())
{
long long now = q.front();
q.pop();
if(now % n == 0)
{
cout<<now<<endl;
return ;
}
q.push(now*10);
q.push(now*10+1);
}
}
int main()
{
while(cin>>n && n)
{
while(!q.empty())
q.pop();
q.push(1);
bfs();
}
}
#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
struct node
{
string s;
int mod;
}cur,nxt;
bool v[1000001];
queue<node>q;
int main()
{
int n;
scanf("%d",&n);
cur.s="1";cur.mod=1;
q.push(cur);
while(!q.empty())
{
cur=q.front();
q.pop();
nxt.mod=(cur.mod*10)%n;
nxt.s=cur.s+'0';
if(nxt.mod==0)
{
cout<<nxt.s;
return 0;
}
if(!v[nxt.mod])
{
q.push(nxt);
v[nxt.mod]=true;
}
nxt.mod=(cur.mod*10+1)%n;
nxt.s=cur.s+'1';
if(nxt.mod==0)
{
cout<<nxt.s;
return 0;
}
if(!v[nxt.mod])
{
q.push(nxt);
v[nxt.mod]=true;
}
}
return 0;
}
迷宫问题（打印路径
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N = 7;
int a[N][N];
bool vis[N][N];
int prex[N*N];
int prey[N*N];
int xx[4] = {0,0,1,-1};
int yy[4] = {1,-1,0,0};
struct Node{
int x;
int y;
int to;
int nex;
}node[50];
int pd(int x,int y)
{
if(x >= 0 && x < 5 && y >= 0 && y <5 && a[x][y] == 0)
return 1;
return 0;
}
void BFS(int x,int y)
{
queue<Node>q;
int tot = 0;
Node st;
node[0].x = node[0].y = 4;
node[0].to = node[0].nex = 0;
q.push(node[0]);
vis[4][4] = 1;
while(!q.empty())
{
Node now = q.front();
q.pop();
if(now.x == 0 && now.y == 0)
{
int t = now.to;
while(1)
{
printf("(%d, %d)\n",node[t].x,node[t].y);
if(!t)
{
return ;
}
t = node[t].nex;
}
}
for(int i=0;i<4;i++)
{
int tx = now.x + xx[i];
int ty = now.y + yy[i];
if(pd(tx,ty) && !vis[tx][ty])
{
vis[tx][ty] = 1;
node[++tot].x = tx;
node[tot].y = ty;
node[tot].to = tot;
node[tot].nex = now.to;
q.push(node[tot]);
}
}
}
}
int main()
{
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
scanf("%d",&a[i][j]);
}
}
BFS(0,0);
return 0;
}