bfs／无向图的最短路径算法

uva,572

简单dfs题目。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 
 6 using namespace std;
 7 const int maxn=105;
 8 
 9 char map[maxn][maxn];
10 int vis[maxn][maxn];
11 int n,m;
12 int dx[]={-1,0,-1,-1,0,1,1,1},dy[]={-1,-1,0,1,1,-1,0,1};
13 
14 bool check(int x,int y)
15 {
16     if(x<0 || x>=m || y<0 || y>=n) return false;
17     if(vis[x][y]) return false;
18     if(map[x][y]!='@') return false;
19     return true;
20 }
21 
22 void dfs(int x,int y)
23 {
24     int xx,yy;
25     vis[x][y]=1;
26     map[x][y]='#';
27     for(int i=0;i<8;i++)
28     {
29         xx=x+dx[i];
30         yy=y+dy[i];
31         if(check(xx,yy))
32         {
33             dfs(xx,yy);
34         }
35     }
36     
37 }
38 
39 
40 int main()
41 {
42     while(scanf("%d %d",&m,&n) && n+m)
43     {
44         memset(map,0,sizeof(map));
45         for(int i=0;i<m;i++)
46             scanf("%s",map[i]);
47         
48         memset(vis,0,sizeof(vis));
49         int cnt=0;
50         for(int i=0;i<m;i++)
51             for(int j=0;j<n;j++)
52             {
53                 if(!vis[i][j] && map[i][j]=='@')
54                 {
55                     dfs(i,j);
56                     cnt++;
57                 }
58             }
59         printf("%d
",cnt);
60     }
61     return 0;
62 }

View Code

uva,439

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 struct Node
 8 {
 9     int x,y;
10     int bu;
11 }q[11111];
12 
13 int dx[]={1,1,-1,-1,2,2,-2,-2},dy[]={2,-2,2,-2,1,-1,1,-1};
14 int vis[15][15];
15 int x,y,xx,yy;
16 char a[3],b[3];
17 int cnt;
18 
19 
20 bool check(int x,int y)
21 {
22     if(x<1 || x>8 || y<1 || y>8) return false;
23     if(vis[x][y]) return false;
24     return true;
25 }
26 
27 void bfs(int x,int y)
28 {
29     int head=0,tail=0;
30     q[head].x=x;
31     q[head++].y=y;
32     vis[x][y]=1;
33     for(int i=0;i<11111;i++)
34         q[i].bu=9999;
35     q[tail].bu=0;
36     while(tail!=head)
37     {
38         Node t=q[tail++];
39         Node tt;
40         for(int i=0;i<8;i++)
41         {
42             tt.x=t.x+dx[i];
43             tt.y=t.y+dy[i];
44             if(tt.x==xx && tt.y==yy)
45             {
46                 cnt=t.bu+1;
47                 return;
48             }
49             if(check(tt.x,tt.y))
50             {
51                 vis[tt.x][tt.y]=1;
52                 tt.bu=t.bu+1;  //应该是求深度。。我一开始直接弄一个cnt++
53 //弄成求附近有多少步了。。wa了两次
54                 q[head++]=tt;
55             }
56         }
57     }
58 }
59 
60 int main()
61 {
62     while(~scanf("%s%s",a, b))
63     {
64         x=a[0]-'a'+1;
65         y=a[1]-'0';
66         xx=b[0]-'a'+1;
67         yy=b[1]-'0';
68         cnt=0;
69         if(x==xx && y==yy)
70             printf("To get from %s to %s takes 0 knight moves.
",a,b);
71         else
72         {
73             memset(q,0,sizeof(q));
74             memset(vis,0,sizeof(vis));
75             bfs(x,y);
76             printf("To get from %s to %s takes %d knight moves.
",a,b,cnt);
77         }
78     }
79     return 0;
80 }

View Code

uva,417

注意dfs递归打表，方法好巧妙＝＝忍不住多写了几遍

－－再写一遍；

void dfs(int s,int n,int t)

{

　　if(n==t)

　　{

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

　　　　　　answ[Count][i]=save[i];

　　　　answ[Count++][t]=0;
　　}

　　else

　　{

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

　　　　{　　

　　　　　　if(!used[i])

　　　　　　{

　　　　　　　　used[i]=1;

　　　　　　　　save[n]='a'+i;

　　　　　　　　dfs(i+1,n+1,t);　

　　　　　　　　　used[i]=0;

　　　　　　}

　　　　}
　　}

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <map>
 5 #include <cstdio>
 6 
 7 using namespace std;
 8 
 9 int used[26];
10 char save[6],data[6];
11 char answ[83685][6];
12 int Count=0;
13 map<string,int> mp;
14 
15 void dfs(int s,int n,int t)
16 {
17     if(n==t)
18     {
19         for(int i=0;i<t;i++)
20             answ[Count][i]=save[i];
21         answ[Count++][t]=0;
22     }
23     else
24     {
25         for(int i=s;i<26;i++)
26         {
27             if(!used[i])
28             {
29                 used[i]=1;
30                 save[n]=i+'a';
31                 dfs(i+1,n+1,t);
32                 used[i]=0;
33             }
34         }
35     }
36 }
37 
38 int main()
39 {
40     Count=1;
41     for(int i=1;i<6;i++)
42         dfs(0,0,i);
43     for(int i=1;i<Count;++i)
44     {
45         string s=answ[i];
46         mp[s]=i;
47     }
48     while(cin>>data)
49     {
50         cout<<mp[data]<<endl;
51     }
52     return 0;
53 }

View Code

uva,352

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 
 6 using namespace std;
 7 const int maxn=105;
 8 
 9 char map[maxn][maxn];
10 int vis[maxn][maxn];
11 int n;
12 int dx[]={-1,0,-1,-1,0,1,1,1},dy[]={-1,-1,0,1,1,-1,0,1};
13 
14 bool check(int x,int y)
15 {
16     if(x<0 || x>=n || y<0 || y>=n) return false;
17     if(vis[x][y]) return false;
18     if(map[x][y]!='1') return false;
19     return true;
20 }
21 
22 void dfs(int x,int y)
23 {
24     int xx,yy;
25     vis[x][y]=1;
26     map[x][y]=0;  //记得标记
27     for(int i=0;i<8;i++)
28     {
29         xx=x+dx[i];
30         yy=y+dy[i];
31         if(check(xx,yy))
32         {
33             dfs(xx,yy);
34         }
35     }
36     
37 }
38 
39 
40 int main()
41 {
42     int test=1;
43     while(~scanf("%d",&n) && n)
44     {
45         memset(map,0,sizeof(map));
46         for(int i=0;i<n;i++)
47             scanf("%s",map[i]);
48         
49         memset(vis,0,sizeof(vis));
50         int cnt=0;
51         for(int i=0;i<n;i++)
52             for(int j=0;j<n;j++)
53             {
54                 if(!vis[i][j] && map[i][j]=='1')
55                 {
56                     dfs(i,j);
57                     cnt++;
58                 }
59             }
60         printf("Image number %d contains %d war eagles.
",test++,cnt);
61     }
62     return 0;
63 }

View Code

uva,336

一开始一根筋想用dfs解出来，因为就30个点

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <map>
 5 #include <vector>
 6 #include <algorithm>
 7 #include <cmath>
 8 #include <queue>
 9 using namespace std;
10 
11 vector<int> vt[32];
12 map<int,int> mp;
13 int dis[32];
14 
15 void dfs(int node,int dp)
16 {
17     if(!dp)
18         return;
19     for(int i=0;i<vt[node].size();i++)
20     {
21         if(!dis[vt[node][i]])
22         {
23             dis[vt[node][i]]=1;
24             dfs(vt[node][i],dp-1);
25         }
26     }
27 }
28 
29 
30 int main()
31 {
32     int nc;
33     int x,y,c;
34     int st;
35     int t=1;
36     int cnt;
37     int strt,ttl;
38     while(scanf("%d",&nc) && nc)
39     {
40         int a,b;
41         mp.clear();
42         c=0;
43         for(int i=0;i<nc;i++)
44         {
45             scanf("%d %d",&a,&b);
46             if(mp.find(a)!=mp.end())
47                 x=mp[a];
48             else
49             {
50                 mp[a]=++c;
51                 x=c;
52             }
53             if(mp.find(b)!=mp.end())
54                 y=mp[b];
55             else
56             {
57                 mp[b]=++c;
58                 y=c;
59             }
60             vt[x].push_back(y);
61             vt[y].push_back(x);
62         }
63         
64         while(scanf("%d %d",&strt,&ttl) && strt+ttl)
65         {
66             memset(dis,0,sizeof(dis));
67             st=mp[strt];
68             cnt=0;
69             dis[st]=1;
70             dfs(st,ttl);
71             for(int i=1;i<=c;i++)
72             {
73                 if(!dis[i])
74                     cnt++;
75             }
76             printf("Case %d: %d nodes not reachable from node %d with TTL = %d.
",t++,cnt,strt,ttl);
77         }
78         for(int i=1;i<=c;i++)
79             vt[i].clear();
80     }
81     return 0;
82 }

dfs代码，wa了三小时，找不出原因

用bfs重写了，把每个节点的深度打表，没有访问到的节点和深度大于给定节点的都是不可达的。

map映射感觉写的好赞

搜点具体那个点到点用dfs，铺面用bfs做

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <map>
 5 #include <vector>
 6 #include <algorithm>
 7 #include <cmath>
 8 #include <queue>
 9 using namespace std;
10 
11 vector<int> vt[32];
12 map<int,int> mp;
13 int dis[32];
14 queue<int> q;
15 
16 void bfs()
17 {
18     int node;
19     while(!q.empty())
20     {
21         node=q.front();
22         q.pop();
23         
24         for(int i=0;i<vt[node].size();i++)
25         {
26             if(dis[vt[node][i]]==-1)
27             {
28                 dis[vt[node][i]]=dis[node]+1;
29                 q.push(vt[node][i]);
30             }
31         }
32     }
33     return;
34 }
35 
36 
37 int main()
38 {
39     int nc;
40     int x,y,c;
41     int st;
42     int t=1;
43     int cnt;
44     int strt,ttl;
45     while(scanf("%d",&nc) && nc)
46     {
47         int a,b;
48         mp.clear();
49         c=0;
50         for(int i=0;i<nc;i++)
51         {
52             scanf("%d %d",&a,&b);
53             if(mp.find(a)!=mp.end())
54                 x=mp[a];
55             else
56             {
57                 mp[a]=++c;
58                 x=c;
59             }
60             if(mp.find(b)!=mp.end())
61                 y=mp[b];
62             else
63             {
64                 mp[b]=++c;
65                 y=c;
66             }
67             vt[x].push_back(y);
68             vt[y].push_back(x);
69         }
70         
71         while(scanf("%d %d",&strt,&ttl) && strt+ttl)
72         {
73             memset(dis,-1,sizeof(dis));
74             st=mp[strt];
75             cnt=0;
76             dis[st]=0;
77             q.push(st);
78             bfs();
79             for(int i=1;i<=c;i++)
80             {
81                 if(dis[i]==-1 || dis[i]>ttl)
82                     cnt++;
83             }
84             printf("Case %d: %d nodes not reachable from node %d with TTL = %d.
",t++,cnt,strt,ttl);
85         }
86         for(int i=1;i<=c;i++)
87             vt[i].clear();
88     }
89     return 0;
90 }

View Code

uva,532

挺简单的bfs题目，只是有几个点该注意

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 using namespace std;
  5 
  6 struct Node
  7 {
  8     int x,y,z;
  9 }q[30000];  //注意数组越界
 10 
 11 int dxyz[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
 12 
 13 char map[32][32][32];
 14 int L,R,C;
 15 int x2,y2,z2;
 16 int x1,y1,z1;
 17 int vis[32][32][32];
 18 int dir[32][32][32];
 19 bool flag;
 20 
 21 bool check(int x,int y,int z)
 22 {
 23     if(x<0 || x>=L || y<0 || y>=R || z<0 || z>=C) return false;
 24     if(vis[x][y][z]) return false;
 25     if(map[x][y][z]!='.') return false;
 26     return true;
 27 }
 28 
 29 
 30 void bfs(int x,int y,int z)
 31 {
 32     int tail=0,head=0;
 33     q[head].x=x;
 34     q[head].y=y;
 35     q[head++].z=z;
 36     vis[0][0][0]=1;
 37     while(tail!=head)
 38     {
 39         Node t=q[tail++];
 40         Node tt;
 41         for(int i=0;i<6;i++)
 42         {
 43             tt.x=t.x+dxyz[i][0];
 44             tt.y=t.y+dxyz[i][1];
 45             tt.z=t.z+dxyz[i][2];
 46             if(tt.x==x2 && tt.y==y2 && tt.z==z2)
 47             {
 48                 dir[tt.x][tt.y][tt.z]=dir[t.x][t.y][t.z]+1;
 49                 flag=true;
 50                 return;
 51             }
 52             if(check(tt.x,tt.y,tt.z))
 53             {
 54                 dir[tt.x][tt.y][tt.z]=dir[t.x][t.y][t.z]+1;
 55                 vis[tt.x][tt.y][tt.z]=1;
 56                 q[head++]=tt;
 57             }
 58         }
 59     }
 60 }
 61 
 62 int main()
 63 {
 64     while(scanf("%d %d %d",&L,&R,&C) && L+R+C)
 65     {
 66         getchar();
 67         memset(map,0,sizeof(map));
 68         for(int i=0;i<L;i++)
 69         {
 70             for(int j=0;j<R;j++)
 71             {
 72                 scanf("%s",map[i][j]);
 73                 for(int k=0;k<C;k++)
 74                 {
 75                     if(map[i][j][k]=='S')  //纪录起点，wa了几次。
 76                     {
 77                         x1=i;
 78                         y1=j;
 79                         z1=k;
 80                     }
 81                     if(map[i][j][k]=='E') //纪录终点，runtime error了几次
 82                     {
 83                         x2=i;
 84                         y2=j;
 85                         z2=k;
 86                     }
 87                 }
 88             }
 89             getchar();
 90         }
 91         memset(vis,0,sizeof(vis));
 92         memset(dir,0,sizeof(dir));
 93         flag=false;
 94         bfs(x1,y1,z1);
 95         if(flag)
 96             printf("Escaped in %d minute(s).
",dir[x2][y2][z2]);
 97         else
 98             printf("Trapped!
");
 99     }
100     return 0;
101 }

View Code

活在现实，做在梦里。