刷题记录 kuangbin带你飞专题一：简单搜索dfsRakiJ的博客-

两天肝完
感觉自己的暴力水平上升了
码力大仙！！！

A.POJ1321 棋盘问题

有一个坑点就是可能相邻层没有棋盘，所以直接搜全部

#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<queue> #include<vector> using namespace std; int n,m; int dx[]={0,1,1,1,-1,-1,-1,0,0}; int dy[]={0,1,-1,0,1,-1,0,1,-1}; char a[15][15]; int zx[1005]; int zy[1005],vis[1005]; int t[20][20]; int ans; void fuck(); void dfs(int x,int num){ if(num==0){   ans++; return; } for(int i=x;i<n;i++){ for(int j=0;j<n;j++){ if(a[i][j]=='#'&&vis[j]==0){     vis[j]=1; dfs(i+1,num-1);     vis[j]=0; } } } return; } int main(){ while(scanf("%d%d",&n,&m)){ if(n==-1&&m==-1)break; for(int i=0;i<n;i++){ scanf("%s",&a[i]); } memset(vis,0,sizeof(vis));   ans=0; dfs(0,m);   cout<<ans<<endl; } return 0; } 

B.POJ 2251 Dungeon Master

裸三维BFS，没有坑点
就是POJ很神奇，把bfs过程直接暴力就让我MLE？
让我学会了能不写在主函数里就一定写外面

#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<queue> #include<vector> using namespace std; int n,m,k; char a[35][35][35]; int vis[35][35][35]; int ans; int sx,sy,sz,zx,zy,zz; int base[6][3] = { {-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,-1},{0,0,1} }; struct node{ int x,y,z,bu; friend bool operator<(node a,node b) { return a.bu>b.bu; } }; bool zou(int x,int y,int z){ if(x<1||x>k)return false; if(y<1||y>m)return false; if(z<1||z>n)return false; return true; } int main(){ while(scanf("%d%d%d",&n,&m,&k)){ if(n==0&&m==0&&k==0)break; int fa=0; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ for(int t=1;t<=k;t++){      cin>>a[t][j][i]; if(a[t][j][i]=='S'){       sx=t;       sy=j;       sz=i; } if(a[t][j][i]=='E'){       zx=t;       zy=j;       zz=i;       a[t][j][i]='.'; } } } }   priority_queue<node>q;   q.push((node){sx,sy,sz,0}); while(!q.empty()){    node x=q.top();    q.pop(); if(x.x==zx&&x.y==zy&&x.z==zz){ printf("Escaped in %d minute(s).n",x.bu);     fa=1; break; } for(int i=0;i<6;i++){ int xx=x.x+base[i][0]; int yy=x.y+base[i][1]; int zz=x.z+base[i][2]; if(zou(xx,yy,zz)&&a[xx][yy][zz]!='#'&&vis[xx][yy][zz]==0){      vis[xx][yy][zz]=1;      q.push((node){xx,yy,zz,x.bu+1}); } } } if(fa==0)printf("Trapped!n"); } return 0; } 

C.POJ 3278 Catch That Cow

一维BFS
控制好边界就行，纯手速秒杀题
（某秒因为边界RE了十多发）

#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<queue> #include<vector> using namespace std; int n,m,k; int a[100005]; struct node { int x,num; }; int vis[100005]; int main(){  cin>>n>>m;  queue<node>q;  q.push((node){n,0});  vis[n]=1; while(!q.empty()){   node x=q.front();   q.pop(); if(x.x==m){    cout<<x.num; return 0; } if(x.x+1<=100000&&x.x+1>=0&&vis[x.x+1]==0){    q.push((node){x.x+1,x.num+1});    vis[x.x+1]=1; } if(x.x-1<=100000&&x.x-1>=0&&vis[x.x-1]==0){    q.push((node){x.x-1,x.num+1});    vis[x.x-1]=1; } if(x.x*2<=100000&&x.x*2>=0&&vis[x.x*2]==0){    q.push((node){x.x*2,x.num+1});    vis[x.x*2]=1; } } return 0; } 

D.POJ 3279 Fliptile

经典开关问题，让我第一次接触到了状态压缩hhh
如果会状压好像也就是个暴力了

#include <cstdio> #include <cstring> #include <queue> #include <iostream> using namespace std; int m,n; int a[20][20],cal[20][20],out[20][20]; const int dx[]={0,0,1,-1,0}; const int dy[]={1,-1,0,0,0}; int zt(int x,int y){ int temp=a[x][y]; for(int i=0;i<5;i++){ int xx=x+dx[i]; int yy=y+dy[i]; if(xx<1||yy<1||xx>n||yy>m)continue;   temp+=cal[xx][yy]; } return temp%2; } int dfs(){ for(int i=2;i<=n;i++){ for(int j=1;j<=m;j++){ if(zt(i-1,j)){     cal[i][j]=1; } } } for(int i=1;i<=m;i++){ if(zt(n,i))return -1; } int res=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){    res+=cal[i][j]; } } return res; } int main(){  cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){    cin>>a[i][j]; } } int fa=0; int ans=0x3f3f3f3f; for(int i=0;i<1<<m;i++){ memset(cal,0,sizeof(cal)); for(int j=1;j<=m;j++){    cal[1][m-j+1]=i>>(j-1)&1; } int c=dfs(); if(c>=0&&c<ans){    fa=1;    ans=c; memcpy(out,cal,sizeof(cal)); } } if(!fa)cout<<"IMPOSSIBLE"<<endl; else{ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(j!=1)cout<<" ";     cout<<out[i][j]; }    cout<<endl; } } return 0; } 

E.POJ 1426 Find The Multiple

思路就是直接暴力构造搜 *10 和 *10+1
判断是否能整除

#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<queue> #include<vector> #define int long long using namespace std; int n,m,k,c; void dfs(unsigned long long x,int t){ if(t>19)return; if(c==1)return; if(x%n==0){   cout<<x<<endl;   c=1; return; } dfs(x*10,t+1); dfs(x*10+1,t+1); return; } signed main(){ while(1){   cin>>n;   c=0; if(n==0)break; dfs(1,0); } return 0; } 

F.POJ 3126 Prime Path

一个有点意思的搜索，不过难度不大，思路就先跑一遍欧拉筛，然后写一个更换数字的函数，暴力循环判断是否为素数，加入队列中就ok了

#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<queue> #include<vector> #define int long long using namespace std; int n,m,k,c; int prime[10005]; bool sf[10005]; const int maxn=10005; int vis[10005]; int cnt=1; void sushu(){ int num=0; memset(sf,true,sizeof(sf)); for(int i=2;i<=maxn;i++){ if(sf[i]) prime[++num]=i; for(int j=1;j<=num;j++){ if(i*prime[j]>maxn) break;              sf[i*prime[j]]=false; if(i%prime[j]==0) break; } }     sf[1]=false;     sf[0]=false; } int bian(int x,int t,int c){ int ge,shi,bai,qian;  ge=x%10;  x/=10;  shi=x%10;  x/=10;  bai=x%10;  qian=x/=10; if(t==1)return c*1000+bai*100+shi*10+ge; else if(t==2)return qian*1000+c*100+shi*10+ge; else if(t==3)return qian*1000+bai*100+c*10+ge; else if(t==4)return qian*1000+bai*100+shi*10+c; } struct node{ int x,num; }; void bfs(int x){  queue<node>q;  q.push((node){x,0});  vis[x]=1; while(!q.empty()){   node u=q.front();   q.pop(); if(u.x==m){    cout<<u.num<<endl; return; } for(int i=1;i<=4;i++){ for(int j=0;j<=9;j++){ if(i==4&&(j==2||j==4||j==6||j==8))continue; if(i==1&&j==0)continue; int tt=bian(u.x,i,j); if(sf[tt]==true&&vis[tt]==0){      q.push((node){tt,u.num+1});      vis[tt]=1; } } } } } signed main(){  cin>>k; sushu(); // if(sf[50])cout<<"1"; // else cout<<"0"; while(k--){   cin>>n>>m; if(n==m){    cout<<"0"<<endl; continue; } memset(vis,0,sizeof(vis)); bfs(n); } return 0; } 

G.POJ 3087 Shuffle’m Up

傻逼题，难度不够，英语来凑，直接模拟就行

#include <cstdio> #include <cstring> #include <queue> #include <iostream> #include <map> using namespace std; int n,c; string a,b,de; void dfs(int x){  map<string,int>m;  string t=a+b; int step=0; while(m[t]==0&&t!=de){ int k=0;   m[t]=1;   step++;   string str=t; for(int i=0;i<c;i++){    str[k]=t[i+c];    k++;    str[k]=t[i];    k++; }   t=str; } if(t==de){   cout<<x<<" "<<step<<endl; } else{   cout<<x<<" "<<"-1"<<endl; } } int main(){  cin>>n; int kk=0; while(n--){   kk++;   cin>>c;   cin>>a>>b>>de; dfs(kk); } return 0; } 

H.POJ 3414 Pots

这题真的是个超级码力题
写完就感觉自己码力很猛
暴力判断八种情况，我这里开结构体里面放了一个数组表示第一和第二个杯子，并用vector来保存路径

#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> using namespace std; void fuck(); void shit(); int a,b,c,n,m; bool vis[102][102]; struct node{ int w[2],num;  vector<string>v; }; int fill(int x,int c){ return c; } int drop(int x){ return 0; } void bfs(int x,int b,int c){  node t; int fa=0;  t.w[0]=0;  t.w[1]=0;  t.num=0;  vis[0][0]=false;  queue<node>q;  q.push(t); while(!q.empty()){   node t=q.front();   q.pop(); if(t.w[0]==c||t.w[1]==c){    cout<<t.num<<endl; for(int i=0;i<t.v.size();i++){     cout<<t.v[i]<<endl; }    fa=1; return; } if(vis[fill(1,a)][t.w[1]]==true){    vis[fill(1,a)][t.w[1]]=false;    node a=t;    a.w[0]=fill(1,x);    a.num++;    a.v.push_back("FILL(1)");    q.push(a); } if(vis[t.w[0]][fill(2,b)]==true){    vis[t.w[0]][fill(2,b)]=false;    node a=t;    a.w[1]=fill(2,b);    a.num++;    a.v.push_back("FILL(2)");    q.push(a); } if(vis[0][t.w[1]]==true){    vis[0][t.w[1]]=false;     node a=t;    a.w[0]=0;    a.num++;    a.v.push_back("DROP(1)");    q.push(a); } if(vis[t.w[0]][0]==true){    vis[t.w[0]][0]=false;    node a=t;    a.w[1]=0;    a.num++;    a.v.push_back("DROP(2)");    q.push(a); } if(t.w[0]+t.w[1]>b){ int cha=t.w[0]+t.w[1]-b; if(vis[cha][b]==true){     vis[cha][b]=false;     node a=t;     a.w[0]=cha;     a.w[1]=b;     a.num++;     a.v.push_back("POUR(1,2)");     q.push(a); } } else{ int cha=t.w[0]+t.w[1]; if(vis[0][cha]==true){     vis[0][cha]=false;     node a=t;     a.w[0]=0;     a.w[1]=cha;     a.num++;     a.v.push_back("POUR(1,2)");     q.push(a); } } if(t.w[0]+t.w[1]>x){ int cha=t.w[0]+t.w[1]-x; if(vis[x][cha]==true){     vis[x][cha]=false;     node a=t;     a.w[0]=x;     a.w[1]=cha;     a.num++;     a.v.push_back("POUR(2,1)");     q.push(a); } } else{ int cha=t.w[0]+t.w[1]; if(vis[cha][0]==true){     vis[cha][0]=false;     node a=t;     a.w[0]=cha;     a.w[1]=0;     a.num++;     a.v.push_back("POUR(2,1)");     q.push(a); } } } if(!fa)cout<<"impossible"; return; } int main(){  cin>>a>>b>>c; memset(vis,true,sizeof(vis)); bfs(a,b,c); } 

I.FZU 2150 Fire Game

码力屑题，让我自闭了一下午，不想写

J.UVA 11624 Fire!

对火和人分别bfs，并记录时间，需要注意的坑点是可能有多团火，然后注意边界

#include<bits/stdc++.h> using namespace std; const int dx[4]={1,-1,0,0}; const int dy[4]={0,0,-1,1}; const int inf=99999999; int vis[1505][1505],f[1505][1505]; char a[1505][1505]; int n,m,c,tt; struct node{ int x,y,t; }gg; int main(){ int t; int sx,sy;  cin>>t; while(t--){   cin>>n>>m;   c=0;   queue<node>fire;   queue<node>q; memset(vis,0,sizeof(vis)); memset(a,'.',sizeof(a)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){     cin>>a[i][j];     f[i][j]=inf; if(a[i][j]=='J'){      sx=i;      sy=j; } if(a[i][j]=='F'){      fire.push((node){i,j,0});      vis[i][j]=1; } } } while(!fire.empty()){    node s=fire.front();    fire.pop(); for(int i=0;i<4;i++){ int xx=s.x+dx[i]; int yy=s.y+dy[i]; if(xx>=1&&yy>=1&&xx<=n&&yy<=m&&vis[xx][yy]==0&&a[xx][yy]=='.'){      vis[xx][yy]=1;      f[xx][yy]=s.t+1;      fire.push((node){xx,yy,s.t+1}); } } } memset(vis,0,sizeof(vis));   q.push((node){sx,sy,0});   vis[sx][sy]=1; while(!q.empty()){    node s=q.front();    q.pop(); if((s.x<=1||s.y<=1||s.x>=n||s.y>=m)&&s.t<f[s.x][s.y]){     c++;     cout<<s.t+1<<endl; break; } for(int i=0;i<4;i++){ int xx=s.x+dx[i]; int yy=s.y+dy[i]; if(xx>=1&&yy>=1&&xx<=n&&yy<=m&&vis[xx][yy]==0&&a[xx][yy]=='.'){      vis[xx][yy]=1;      q.push((node){xx,yy,s.t+1}); } } } if(!c){    cout<<"IMPOSSIBLE"<<endl; } } } 

K.POJ 3984 迷宫问题

弱智题

L.HDU 1241 Oil Deposits

问有多少个联通块
直接循环，dfs走过的点变为普通路，dfs的次数就是答案

#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<queue> #include<vector> #define int long long using namespace std; int n,m,k,c; int prime[10005]; bool sf[10005]; const int maxn=10005; int vis[105][105]; char a[1005][1005]; const int dx[]={1,1,1,-1,-1,-1,0,0}; const int dy[]={1,-1,0,1,-1,0,1,-1}; int cnt=1; void dfs(int x,int y){ for(int i=0;i<8;i++){ int xx=x+dx[i]; int yy=y+dy[i]; if(xx>=1&&yy>=1&&xx<=n&&yy<=m&&a[xx][yy]=='@'){    a[xx][yy]='*'; dfs(xx,yy); } } return; } signed main(){ while(1){   cin>>n>>m; int ans=0; if(n==0&&m==0)break; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){     cin>>a[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]=='@'){      a[i][j]='*'; dfs(i,j); //   a[i][j]='*';      ans++; } } }   cout<<ans<<endl; } } 

M.HDU 1495 非常可乐

又是一个码力屑题，纯暴力bfs
如果变量没写好可能容易自闭

#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<queue> #include<vector> using namespace std; int n,m,k,c; int v[5]; struct node{ int v[3],num; node(int x,int y,int z,int st){   v[0]=x;   v[1]=y;   v[2]=z;   num=st; } }; bool vis[102][102][102]; const int d1[6] = {0, 0, 1, 1, 2, 2}; const int d2[6] = {1, 2, 0, 2, 0, 1}; void bfs(){  queue<node>q; memset(vis,true,sizeof(vis));  q.push(node{v[0],0,0,0});  vis[v[0]][0][0]=false; while(!q.empty()){    node x=q.front();    q.pop(); int cnt=0; int dd=v[0]/2; for(int i=0;i<3;i++){ if(x.v[i]==dd){      cnt++; } if(cnt>=2){      cout<<x.num<<endl; return; } } for(int i=0;i<6;i++){     node in=x;     in.num++; if(x.v[d1[i]]){ int cha=v[d2[i]]-x.v[d2[i]]; if(cha>=x.v[d1[i]]){       in.v[d2[i]]+=in.v[d1[i]];       in.v[d1[i]]=0; } else{       in.v[d1[i]]-=cha;       in.v[d2[i]]+=cha; } if(vis[in.v[0]][in.v[1]][in.v[2]]==true){       q.push(in);       vis[in.v[0]][in.v[1]][in.v[2]]=false; } } } } printf("NOn"); } signed main(){ while(scanf("%d%d%d",&v[0],&v[1],&v[2])){ if(v[0]==0&&v[1]==0&&v[2]==0)break; if(v[0]%2==1){    cout<<"NO"<<endl; continue; } bfs(); } return 0; } 

N.HDU 2612 Find a way

跑两个bfs，记录两人到达每一个KFC的时间，最后循环求出最小时间（今晚刚吃KFC）

#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<queue> #include<vector> using namespace std; int n,m,k,c; const int maxn=10005; int vis[205][205]; int cnt,cnt1,cnt2; char a[1005][1005]; const int dx[]={1,-1,0,0}; const int dy[]={0,0,1,-1}; struct node{ int x,y,num; }; int dis[205][205]; signed main(){ while(scanf("%d%d",&n,&m)!=EOF){ int ans=99999999;   vector<int>v1,v2;   c=0; if(n==0&&m==0)break;   cnt=0,cnt1=0,cnt2=0; int sx1,sy1,sx2,sy2; memset(dis,0,sizeof(dis)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){     cin>>a[i][j];     vis[i][j]=0; if(a[i][j]=='Y'){      sx1=i;      sy1=j; } if(a[i][j]=='M'){      sx2=i;      sy2=j; } if(a[i][j]=='@'){      v1.push_back(j);      v2.push_back(i); } } }   queue<node>q;   q.push((node){sx1,sy1,0});   vis[sx1][sy1]=1; while(!q.empty()){    node x=q.front();    q.pop(); if(a[x.x][x.y]=='@'){     dis[x.x][x.y]+=x.num; } for(int j=0;j<4;j++){ int xx=dx[j]+x.x; int yy=dy[j]+x.y; if(xx>=1&&yy>=1&&xx<=n&&yy<=m&&vis[xx][yy]==0&&a[xx][yy]!='#'){      vis[xx][yy]=1;      q.push((node){xx,yy,x.num+1}); } } } while(!q.empty()){    q.pop(); } memset(vis,0,sizeof(vis));   q.push((node){sx2,sy2,0});   vis[sx2][sy2]=1; while(!q.empty()){    node x=q.front();    q.pop(); if(a[x.x][x.y]=='@'){     dis[x.x][x.y]+=x.num; } for(int j=0;j<4;j++){ int xx=dx[j]+x.x; int yy=dy[j]+x.y; if(xx>=1&&yy>=1&&xx<=n&&yy<=m&&vis[xx][yy]==0&&a[xx][yy]!='#'){      vis[xx][yy]=1;      q.push((node){xx,yy,x.num+1}); } } }   ans=99999999; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(dis[i][j]!=0)ans=min(ans,dis[i][j]); } }   cout<<ans*11<<endl; } } 

虽然这个搜索专题难度不大但是码力是真的不小…
搜索（×）锻炼暴力水平（√）
下一个专题：最短路
加油！！！