POJ 3984

【类型】

bfs

【Tip】

当结构体内部有构造函数时,不能定义二维结构体.

【Code】

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
struct node{
    int x,y,sx,sy;
    //node(int xx,int yy,int ssx,int ssy):x(xx),y(yy),sx(ssx),sy(ssy) {}
};
node position[10][10];
queue q;
int vi[6][6]={0};
int maze[5][5]={
    0, 1, 0, 0, 0,
    0, 1, 0, 1, 0,
    0, 0, 0, 0, 0,
    0, 1, 1, 1, 0,
    0, 0, 0, 1, 0,
};

void Bac(int x,int y){
    if(x==-1,y==-1){
        return;
    }
    Bac(position[x][y].x,position[x][y].y);
    printf("(%d, %d)\n",x,y);
}

node Anode(int x,int y,int sx,int sy){
    node A;
    A.x=x;
    A.y=y;
    A.sx=sx;
    A.sy=sy;
    return A;
}

void bfs(){
    position[0][0].x=-1;
    position[0][0].y=-1;
    position[0][0].sx=0;
    position[0][0].sy=0;
    q.push(Anode(-1,-1,0,0));
    vi[0][0]=1;
    while(!q.empty()){
        node a=q.front();
        if(a.sx==4 && a.sy==4){
            Bac(a.sx,a.sy);
            return;
        }
        q.pop();
        if(a.sx+1=0 && !vi[a.sx][a.sy-1]&& !maze[a.sx][a.sy-1]){
            position[a.sx][a.sy-1].sx=a.sx;
            position[a.sx][a.sy-1].sy=a.sy-1;
            position[a.sx][a.sy-1].x=a.sx;
            position[a.sx][a.sy-1].y=a.sy;
            q.push(Anode(a.sx,a.sy,a.sx,a.sy-1));
            vi[a.sx][a.sy-1]=1;
        }
        if(a.sx-1>=0 && !vi[a.sx-1][a.sy]&& !maze[a.sx-1][a.sy]){
            position[a.sx-1][a.sy].sx=a.sx-1;
            position[a.sx-1][a.sy].sy=a.sy;
            position[a.sx-1][a.sy].x=a.sx;
            position[a.sx-1][a.sy].y=a.sy;
            q.push(Anode(a.sx,a.sy,a.sx-1,a.sy));
            vi[a.sx-1][a.sy]=1;
        }
    }
}
int main(){
    bfs();
    return 0;
}

POJ 1321 && 2251

【类型】

dfs,bfs,搜索基础

【来源】

[kuangbin带你飞]专题一 简单搜索 [Cloned]

【Tip】

摘自网上一个blog,一般求最大或者总的xx(方案,步数…)的时候,一般用bfs,如果用dfs的话,你要写很多if来判断.

【Code】

1321

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int chess[15][15];
int vichess[15]={0};
int n,k,cnt,num=0;
char elem;

void dfs(int i){
    if(num==k){
        cnt++;
        return;
    }
    for(int t=i;t<=n;++t)
        for(int j=1;j<=n;++j)
            if(chess[t][j] && !vichess[j]){
                vichess[j]=1;
                num++;
                dfs(t+1);
                vichess[j]=0;
                num–;
            }
}

int main(){
    while(~scanf(“%d %d”,&n,&k) && n!=-1 && k!=-1){
         memset(chess,0,sizeof(chess));
         cnt=0;
         for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                cin>>elem;
                if(elem==’#’)
                    chess[i][j]=1;
            }
         }
        dfs(1);
        printf(“%d\n”,cnt);
    }
    return 0;
}

2251

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
#define maxn 40
using namespace std;

struct Node{
    int x,y,z,t;
    Node(int i,int j,int m,int n):x(i),y(j),z(m),t(n){}//构造
    Node(){}
}pre;

char ma[maxn][maxn][maxn];
int vi[maxn][maxn][maxn];
int L,R,C,sx,sy,sz,ex,ey,ez;
int toward[6][3]={1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1};//六种走向

bool judge(int xx,int yy,int zz){
    if(xx<=0 || xx>L || yy<=0 || yy>R || zz<=0 || zz>C)
        return false;
    return true;
}

void bfs(){
    memset(vi,0,sizeof(vi));
    queue<Node> que;
    que.push(Node(sx,sy,sz,0));
    vi[sx][sy][sz]=1;
    while(!que.empty()){
        pre=que.front(); que.pop();
        if(pre.x==ex && pre.y==ey && pre.z==ez){
            printf(“Escaped in %d minute(s).\n”,pre.t);
            return;
        }
        for(int i=0;i<6;++i){
            int xx=pre.x+toward[i][0];
            int yy=pre.y+toward[i][1];
            int zz=pre.z+toward[i][2];
            if(judge(xx,yy,zz) && !vi[xx][yy][zz] && ma[xx][yy][zz]!=’#’){
                vi[xx][yy][zz]=1;
                que.push(Node(xx,yy,zz,pre.t+1));
            }
        }
    }
    printf(“Trapped!\n”);
}

int main(){
    while(~scanf(“%d%d%d”,&L,&R,&C),L+R+C){
        for(int i=1;i<=L;++i)
            for(int j=1;j<=R;++j)
                scanf(“%s”,ma[i][j]+1);
        for(int i=1;i<=L;++i)
            for(int j=1;j<=R;++j)
                for(int z=1;z<=C;++z)
                    if(ma[i][j][z]==’S’)
                        sx=i,sy=j,sz=z;
                    else if(ma[i][j][z]==’E’)
                        ex=i,ey=j,ez=z;
         bfs();
    }

    return 0;
}