BFS && DFS

HDOJ 1312 Red and Black

http://acm.hdu.edu.cn/showproblem.php?pid=1312

很裸的dfs，在dfs里面写上ans++，能到几个点就调了几次dfs，最后ans就是答案

 #include<cstdio>

 #include<iostream>

 using namespace std;

 char map[][];

 int n,m,si,sj,ans;

 int dir[][] = {{,}, {-,}, {,-}, {,}};

 int dfs(int x, int y)

 {

     if (x<=||x>m||y<=||y>n)

     {

         return ;

     }

     ans++;

     for (int i = ; i < ; ++i)

     {

         if (map[x+dir[i][]][y+dir[i][]] == '.')

         {

             map[x+dir[i][]][y+dir[i][]] = 'X';//把访问过的置为“墙”，以免重复计算

             dfs(x+dir[i][],y+dir[i][]);

         }

     }

 }

 int main()

 {

     while(scanf("%d%d", &n, &m) != EOF)

     {

         if (n ==  && m == )

         {

             break;

         }

         for (int i = ; i <= m; ++i)

         {

             for (int j = ; j <= n; ++j)

             {

                 cin >> map[i][j];

                 if (map[i][j] == '@')

                 {

                     si = i;

                     sj = j;

                 }

             }

         }

         ans = ;

         dfs(si,sj);

         cout << ans << endl;

     }

     return ;

 }

HDOJ 1241 Oil Deposits

http://acm.hdu.edu.cn/showproblem.php?pid=1241

简单dfs 求连通块对地图中的每个@点，ans++调dfs 把和它连通的都标记了

调dfs的次数，就是连通油田的块数

 #include<stdio.h>

 int m,n;

 char map[][];

 int dir[][]={{,},{,-},{,},{-,},{,},{,-},{-,},{-,-}};

 void dfs(int x,int y)

 {

     map[x][y]='*';

     for(int i=;i<;i++)

     {

         int fx=x+dir[i][];

         int fy=y+dir[i][];

         if(fx>=&&fy>=&&fx<m&&fy<n)

         {

             if(map[fx][fy]=='@')

             {

                 dfs(fx,fy);

             }

         }

     }

 }

 int main()

 {

     while(~scanf("%d%d",&m,&n))

     {

         int ans=;

         if(m==)  break;

         getchar();

         for(int i=;i<m;i++)

         {

             for(int j=;j<n;j++)

             {

                 scanf("%c",&map[i][j]);

             }

             getchar();

         }

         for(int i=;i<m;i++)

         {

             for(int j=;j<n;j++)

             {

                 if(map[i][j]=='@')

                 {

                     ans++;

                     dfs(i,j);

                 }

             }

         }

         printf("%d\n",ans);

     }

     return ;

 }

COJ 1224 ACM小组的古怪象棋

http://122.207.68.93/OnlineJudge/problem.php?id=1224

马吃将最少要几步...而且这个将还是不会动的...

 #include<cstdio>

 #include<cstring>

 #include<queue>

 using namespace std;

 int n,m,x,y,si,sj,ans;

 int map[][];//这里map实际上起到的是vis的作用

 int dir[][]={,,,,,-,,-,-,-,-,-,-,,-,};

 struct node

 {

     int x,y,d;

 };

 int bfs()

 {

     queue<node> q;

     while(!q.empty()) q.pop();

     node now,next;

     now.x=si;

     now.y=sj;

     now.d=;

     q.push(now);

     map[now.x][now.y]=;

     while(!q.empty())

     {

         now = q.front();

         if(now.x==x&&now.y==y) return now.d;

         q.pop();

         for (int i = ; i < ; ++i)

         {

             next.x=now.x+dir[i][];

             next.y=now.y+dir[i][];

             if(next.x>=&&next.x<n&&next.y>=&&next.y<m&&map[next.x][next.y]==)

             {

                 next.d=now.d+;

                 q.push(next);

                 map[next.x][next.y]=;

             }

         }

     }

     return -;

 }

 int main()

 {

     while(scanf("%d%d%d%d%d%d",&n,&m,&x,&y,&si,&sj)!=EOF)

     {

         memset(map,,sizeof(map));

         ans = bfs();

         if(ans==-) printf("-1\n");

         else printf("%d\n", ans);

     }

     return ;

 }

拿双向BFS也写了一个 AC了不过我总感觉怪怪的...

 #include<cstdio>

 #include<queue>

 #include<cstring>

 using namespace std;

 int n,m,si,sj,ei,ej;

 int dir[][]={,,,,,-,,-,-,-,-,-,-,,-,};

 int vis[][],mi[][];//vis 0表示尚未访问过 1表示被正向bfs扫到过 2表示被反向bfs扫到

 struct node                //mi保存到达这个点的最小步数 以便两个bfs相遇时读出步数

 {                          //具体就是一层一层地扫了 遇到了(1遇见2 或者 2遇见1)就立即返回

     int x,y,d;

 };

 bool check(int x,int y)

 {

     if(x>&&x<=n&&y>&&y<=m) return true;

     return false;

 }

 int bfs()

 {

     queue<node> q1,q2;

     while(!q1.empty()) q1.pop();

     while(!q2.empty()) q2.pop();

     node now,next;

     now.x=si;

     now.y=sj;

     now.d=;

     q1.push(now);

     mi[si][sj]=;

     now.x=ei;

     now.y=ej;

     now.d=;

     q2.push(now);

     mi[ei][ej]=;

     while(!q1.empty()||!q2.empty())

     {

         if(!q1.empty())

         {

             now=q1.front();

             q1.pop();

             if(vis[now.x][now.y]==) continue;

             if(vis[now.x][now.y]==) return now.d+mi[now.x][now.y];

             vis[now.x][now.y]=;

             for(int i=;i<;i++)

             {

                 next.x=now.x+dir[i][];

                 next.y=now.y+dir[i][];

                 if(check(next.x,next.y)&&vis[next.x][next.y]!=)

                 {

                     if(vis[next.x][next.y]==) return now.d+mi[next.x][next.y]+;

                     else

                     {

                         next.d=now.d+;

                         mi[next.x][next.y]=next.d;

                         q1.push(next);

                     }

                 }

             }

         }

         //

         if(!q2.empty())

         {

             now=q2.front();

             q2.pop();

             if(vis[now.x][now.y]==) continue;

             if(vis[now.x][now.y]==) return now.d+mi[now.x][now.y];

             vis[now.x][now.y]=;

             for(int i=;i<;i++)

             {

                 next.x=now.x+dir[i][];

                 next.y=now.y+dir[i][];

                 if(check(next.x,next.y)&&vis[next.x][next.y]!=)

                 {

                     if(vis[next.x][next.y]==) return now.d+mi[next.x][next.y]+;

                     else

                     {

                         next.d=now.d+;

                         mi[next.x][next.y]=next.d;

                         q2.push(next);

                     }

                 }

             }

         }

     }

     return -;

 }

 int main()

 {

     while(scanf("%d%d%d%d%d%d",&n,&m,&si,&sj,&ei,&ej)!=EOF)

     {

         memset(vis,,sizeof(vis));

         memset(mi,-,sizeof(mi));

         printf("%d\n", bfs());

     }

     return ;

 }

COJ 1259 跳跳

http://122.207.68.93/OnlineJudge/problem.php?id=1259

为数字2到9的都建一个队列，读地图时候遇到了就加到各自的队列里

在bfs主体中，如果探索到了2到9的数字，就把相应队列里的结点顺便一并添加到bfs的主队列中...

 #include<cstdio>

 #include<queue>

 #include<cstring>

 #define REP(i,a,b) for(int i = a; i < b; i++)

 using namespace std;

 char map[][];

 int vis[][];

 int dir[][]={,,-,,,,,-};

 int n,si,sj,ei,ej,ans;

 queue<int> q[];

 struct node

 {

     int x,y,d;

 }now,next;

 int bfs()

 {

     queue<node> qq;

     while(!qq.empty()) qq.pop();

     now.x=si;

     now.y=sj;

     now.d=;

     qq.push(now);

     while(!qq.empty())

     {

         now=qq.front();

         qq.pop();

         if(now.x==ei&&now.y==ej) return now.d;

         if(vis[now.x][now.y]) continue;

         vis[now.x][now.y]=;

         REP(i,,) {

             next.x=now.x+dir[i][];

             next.y=now.y+dir[i][];

             if(next.x>=&&next.x<n&&next.y>=&&next.y<n&&map[next.x][next.y]!=''&&vis[next.x][next.y]==)

             {

                 if(map[next.x][next.y]=='')

                 {

                     next.d=now.d+;

                     qq.push(next);

                 }else

                 {

                     int a=map[next.x][next.y]-'';

                     if(a>=&&a<=)

                     {

                         next.d=now.d+;

                         qq.push(next);

                         while(!q[a-].empty())

                         {

                             next.x=q[a-].front();

                             q[a-].pop();

                             next.y=q[a-].front();

                             q[a-].pop();

                             next.d=now.d+;

                             qq.push(next);

                         }

                     }

                 }

             }

         }

     }

     return -;

 }

 int main()

 {

     while(scanf("%d",&n)!=EOF)

     {

         REP(i,,) {

             while(!q[i].empty()) q[i].pop();

         }

         getchar();

         memset(vis,,sizeof(vis));

         REP(i,,n) {

             REP(j,,n) {

                 scanf("%c",&map[i][j]);

                 if(map[i][j]=='S')

                 {

                     si=i;

                     sj=j;

                 }else if(map[i][j]=='E')

                 {

                     ei=i;

                     ej=j;

                 }else if((map[i][j]-'')>=&&(map[i][j]-'')<=)

                 {

                     q[(map[i][j]-'')-].push(i);

                     q[(map[i][j]-'')-].push(j);

                 }

             }

             getchar();

         }

         map[si][sj]='';

         map[ei][ej]='';

         ans=bfs();

         if(ans==-) printf("Oh No!\n");

         else printf("%d\n", ans);

     }

     return ;

 }

HDOJ 1242 Rescue

http://acm.hdu.edu.cn/showproblem.php?pid=1242

bfs+优先队列

实际上救援可以有多个，而公主只有一个，所以这题应该从公主开始bfs，遇到救援就停止，但是杭电这道题貌似只有一个救援...

 #include <stdio.h>

 #include <string.h>

 #include <vector>

 #include <queue>

 using namespace std;

 char map[][];

 bool flag[][];

 int dx[]={,,-,};

 int dy[]={,,,-};

 int n,m;

 struct node

 {

     int x;

     int y;

     int time;

     friend bool operator<(node a,node b) //优先队列

     {

         return a.time>b.time;   //时间小的先出队

     }

 };

 int BFS(int x,int y)

 {

     priority_queue<node> q;

     node now,next;

     int i;

     now.x=x;

     now.y=y;

     now.time=;

     q.push(now);

     flag[now.y][now.x]=true;

     while(!q.empty())

     {

         now=q.top();

         for(i=;i<;i++)

         {

             next.x=now.x+dx[i];

             next.y=now.y+dy[i];

             if(next.x>=&&next.x<=m&&next.y>=&&next.y<=n&&map[next.y][next.x]!='#'&&flag[next.y][next.x]==false)

             {

                 flag[next.y][next.x]=true;

                 next.time=now.time+;

                 if(map[next.y][next.x]=='x')

                     next.time++;

                 q.push(next);   //next更新后在入队

                 if(map[next.y][next.x]=='a')

                     return next.time;

             }

         }

         q.pop();

     }

     return -;

 }

 int main()

 {

     int i,j,xe,ye;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         vector<node> r;

         r.clear();

         for(i=;i<=n;i++)

         {

             getchar();

             for(j=;j<=m;j++)

             {

                 scanf("%c",&map[i][j]);

             }

         }

         for(i=;i<=n;i++)

         {

             for(j=;j<=m;j++)

             {

                 if(map[i][j]=='r')

                 {

                     node temp;

                     temp.y=i;

                     temp.x=j;

                     temp.time=;

                     r.push_back(temp);

                 }

             }

         }

         int min=;

         for(i=;i<r.size();i++)

         {

             memset(flag,false,sizeof(flag));

             int tem=BFS(r[i].x,r[i].y);

             if(tem<min)

                 min=tem;

         }

         if(min<||r.size()==)   //要判断是否有r，之前没判断，WA了几次

             printf("Poor ANGEL has to stay in the prison all his life.\n");

         else

             printf("%d\n",min);

     }

     return ;

 }

HDOJ 1026 Ignatius and the Princess I

http://acm.hdu.edu.cn/showproblem.php?pid=1026

bfs+记录路径多开一个path[][]用于记录路径并在结构体里增加一对pre指向前一个节点的x，y坐标

然后从终点开始把各个节点入栈，出栈的时候就是从起点到终点了...

 #include <iostream>

 #include <queue>

 #include <stack>

 using namespace std;

 typedef struct Node{

     int x, y, cost;

     int prex, prey;

 }Node;

 int N, M;

 char maze[][];   // 记录初始输入

 Node path[][];   // 记录路径

 int dir[][] = {{-, }, {, }, {, -}, {, }};

 // 判断(x, y)是否可行

 bool isOK(int x, int y)

 {

     if(x>= && x<N && y>= && y<M && maze[x][y]!='X')

         return ;

     else

         return ;

 }

 void Init()

 {

     int i, j;

     for(i = ; i < N; ++i)

         for(j = ; j < M; ++j)

             path[i][j].cost = -;

 }

 void backPath(int x, int y)

 {

     stack<Node> S;

     Node a, b;

     int cc = , tmp;

     cout << "It takes " << path[N - ][M - ].cost

         << " seconds to reach the target position, let me show you the way." << endl;

     a = path[N - ][M - ];

     while()

     {

         if(a.x ==  && a.y == )

             break;

         S.push(a);

         a = path[a.prex][a.prey];

     }

     a = path[][];

     while(!S.empty())

     {

         b = S.top();

         S.pop();

         if(maze[b.x][b.y] == '.')

             cout << cc++ << "s:(" << a.x << "," << a.y << ")->(" << b.x << "," << b.y << ")" << endl;

         else

         {

             cout << cc++ << "s:(" << a.x << "," << a.y << ")->(" << b.x << "," << b.y << ")" << endl;

             tmp = maze[b.x][b.y] - '';

             while(tmp--)

                 cout << cc++ << "s:FIGHT AT (" << b.x << "," << b.y << ")" <<endl;

         }

         a = b;

     }

     cout<<"FINISH"<<endl;

 }

 int BFS(int x, int y)

 {

     queue<Node> Q;

     Node a, b;

     a.x = a.y = a.cost = a.prex = a.prey = ;

     if(maze[][] != '.')

         a.cost = maze[][] - '';

     path[][] = a;

     Q.push(a);

     while(!Q.empty())

     {

         a = Q.front();

         Q.pop();

         for(int i=; i<; ++i)

         {

             b.x = a.x + dir[i][];

             b.y = a.y + dir[i][];

             if(!isOK(b.x, b.y))

                 continue;

             if(maze[b.x][b.y] == '.')

                 b.cost = a.cost + ;

             else

                 b.cost = a.cost + maze[b.x][b.y]-'' + ;

             if(b.cost < path[b.x][b.y].cost || path[b.x][b.y].cost == -)

             {

                 b.prex = a.x;

                 b.prey = a.y;

                 path[b.x][b.y] = b;

                 Q.push(b);

             }

         }

     }

     if(path[N - ][M - ].cost == -)

     {

         cout << "God please help our poor hero." << endl;

         cout << "FINISH" << endl;

         return ;

     }

     backPath(N-, M-);

 }

 int main()

 {

     while(cin >> N >> M)

     {

         memset(maze, , sizeof(maze));

         for(int i=; i<N; ++i)

             for(int j=; j<M; ++j)

                 cin >> maze[i][j];

         Init();

         BFS(, );

     }

     return ;

 }

HDOJ 1195 Open the Lock

http://acm.hdu.edu.cn/showproblem.php?pid=1195

这题相当蛋疼，光是那四位数字在那转换就让我写的菊紧...

这题可以用双向bfs，不过这题数据比较弱，写了个bfs过了，也就没心情优化了...

 #include<cstdio>

 #include<queue>

 #include<cstring>

 #define REP(i,a,b) for(int i = a; i < b; i++)

 using namespace std;

 int T,b,start,end,tmp[],cur[],vis[];

 int cal(int n)

 {

     tmp[]=n/;

     tmp[]=(n%)/;

     tmp[]=(n%)/;

     tmp[]=n%;

     return ;

 }

 int init()

 {

     cur[]=tmp[];

     cur[]=tmp[];

     cur[]=tmp[];

     cur[]=tmp[];

     return ;

 }

 int ans()

 {

     return cur[]*+cur[]*+cur[]*+cur[];

 }

 struct node

 {

     int v,d;

 }now,next;

 int bfs()

 {

     queue<node> q;

     while(!q.empty()) q.pop();

     now.v=start;

     now.d=;

     q.push(now);

     while(!q.empty())

     {

         now=q.front();

         if(now.v==end) return now.d;

         q.pop();

         if(vis[now.v]) continue;

         vis[now.v]=;

         cal(now.v);

         REP(i,,) {

             init();

             cur[i]++;

             if(cur[i]==) cur[i]=;

             next.v=ans();

             if(vis[next.v]) continue;

             next.d=now.d+;

             q.push(next);

         }

         REP(i,,) {

             init();

             cur[i]--;

             if(cur[i]==) cur[i]=;

             next.v=ans();

             if(vis[next.v]) continue;

             next.d=now.d+;

             q.push(next);

         }

         next.v=tmp[]*+tmp[]*+tmp[]*+tmp[];

         next.d=now.d+;

         if(!vis[next.v]) q.push(next);

         next.v=tmp[]*+tmp[]*+tmp[]*+tmp[];

         next.d=now.d+;

         if(!vis[next.v]) q.push(next);

         next.v=tmp[]*+tmp[]*+tmp[]*+tmp[];

         next.d=now.d+;

         if(!vis[next.v]) q.push(next);

     }

     return ;

 }

 int main()

 {

     scanf("%d",&T);

     while(T--)

     {

         memset(vis,,sizeof(vis));

         scanf("%d",&start);

         scanf("%d",&end);

         printf("%d\n", bfs());

     }

     return ;

 }

COJ 1336 Interesting Calculator

http://122.207.68.93/OnlineJudge/problem.php?id=1336

这题是湖南第九届省赛的题，bfs+优先队列写不好的话空间可能会爆

我是多用了一个mi数组存达到这个数需要的最小步骤，如果扩展中遇到这个点，但是此时的d已经比保存的大了，就不扩展此结点...

看是觉得*0和*1 +0这些纯属没用的状态 WA好几次才发现 *0还是有用的...当第二数比第一个小时，要先*0 具体看代码吧

 #include<cstdio>

 #include<queue>

 #include<cstring>

 #define MAXN 100005

 #define REP(i,a,b) for(int i = a; i < b; i++)

 using namespace std;

 int start,end,T=,min_c,min_d;

 int a[],b[],c[];

 int mi[MAXN],vis[MAXN];

 struct Node

 {

     int val,cost,dep;

     friend bool operator<(Node a,Node b)

     {

         if(a.cost==b.cost) return a.dep>b.dep;

         else return a.cost>b.cost;

     }

 }now,next;

 int bfs()

 {

     priority_queue<Node> q;

     while(!q.empty()) q.pop();

     now.cost=;

     now.dep=;

     now.val=start;

     mi[now.val]=;

     q.push(now);

     while(!q.empty())

     {

         now=q.top();

         q.pop();

         if(vis[now.val]) continue;

         vis[now.val]=;

         if(now.val==end)

         {

             min_c=now.cost;

             min_d=now.dep;

             return ;

         }

         REP(i,,) {

             next.val=now.val*+i;

             if(next.val<=end)

             {

                 next.cost=now.cost+a[i];

                 next.dep=now.dep+;

                 if(!vis[next.val]&&mi[next.val]>next.cost)

                 {

                     q.push(next);

                     mi[next.val]=next.cost;

                 }

             }

         }

         REP(i,,) {

             next.val=now.val+i;

             if(next.val<=end)

             {

                 next.cost=now.cost+b[i];

                 next.dep=now.dep+;

                 if(!vis[next.val]&&mi[next.val]>next.cost)

                 {

                     q.push(next);

                     mi[next.val]=next.cost;

                 }

             }

         }

         REP(i,,) {//开始这里i是从2开始的...WA好几发

             next.val=now.val*i;

             if(next.val<=end)

             {

                 next.cost=now.cost+c[i];

                 next.dep=now.dep+;

                 if(!vis[next.val]&&mi[next.val]>next.cost)

                 {

                     q.push(next);

                     mi[next.val]=next.cost;

                 }

             }

         }

     }

     return ;

 }

 int main()

 {

     while(scanf("%d%d",&start,&end)!=EOF)

     {

         T++;

         memset(mi,0x3f,sizeof(mi));

         memset(vis,,sizeof(vis));

         REP(i,,) scanf("%d",&a[i]);

         REP(i,,) scanf("%d",&b[i]);

         REP(i,,) scanf("%d",&c[i]);

         bfs();

         printf("Case %d: %d %d\n",T,min_c,min_d);

     }

 }

POJ 1077 Eight

http://poj.org/problem?id=1077

经典八数码...据说不做此题，人生是不完整的...

判重就是一大难点：这题要用到全排列的变进制hash存储

然后算法的话 bfs可能险超时双向bfs和A*是比较好的选择... 至于代码吗，还没写哈哈...

持续更新中...

巴特西

BFS && DFS

最新文章

热门文章