dfs___刷题记录

poj 1564

给出一个s,n个数，输出所有的能够得到s的方案

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int a[15];
 8 int ans[15];
 9 int n,s,flag;
10 
11 void dfs(int x,int sum,int cnt){
12     if(sum > s) return;
13     if(sum == s){
14         flag = 1;
15         printf("%d",ans[0]);
16         for(int i = 1;i < cnt;i++) printf("+%d",ans[i]);
17         printf("
");
18     }
19     
20     for(int i = x;i < n;i++){
21         ans[cnt] = a[i];
22         dfs(i+1,sum+a[i],cnt+1);
23         while(i+1 < n && a[i] == a[i+1]) i++;
24     }
25 }
26 
27 int main(){
28     while(scanf("%d %d",&s,&n) != EOF && s){
29         for(int i = 0;i < n;i++) scanf("%d",&a[i]);
30         printf("Sums of %d:
",s);
31         flag = 0;
32         dfs(0,0,0);
33         if(!flag) printf("NONE
");
34     }
35     return 0;
36 }

View Code

poj 2488

骑士周游列国

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int res[105][105];
int vis[105][105];

int dir[8][2] = {-2,-1, -2,1, -1,-2, -1,2, 1,-2, 1,2, 2,-1, 2,1};

int m,n;
int flag;

void dfs(int x,int y,int cnt){
    if(flag) return;
    res[cnt][0] = x;res[cnt][1] = y;
    if(cnt == n*m) {
        flag = 1;
        for(int i = 1;i <= n*m;i++)
        printf("%c%d",res[i][0]-1+'A',res[i][1]);
        printf("
");
        return;
    }
    
    for(int i = 0;i < 8;i++){
        int xx = x+ dir[i][0];
        int yy = y+ dir[i][1];
        if(!vis[xx][yy] && xx>0 && xx <= n && yy > 0 && yy <= m){
            vis[xx][yy] = 1;
            dfs(xx,yy,cnt+1);
            vis[xx][yy] = 0;
        }
    }
}

int main(){
    int T;
    scanf("%d",&T);
    int kase = 0;
    while(T--){
        scanf("%d %d",&m,&n);
        
        memset(vis,0,sizeof(vis));
        vis[1][1] = 1;
        
        printf("Scenario #%d:
",++kase); 
        flag = 0;
        dfs(1,1,1);
        
        if(!flag) printf("impossible
");
        if(T) printf("
");

    } 
    return 0;
}

View Code

poj 3009

这道题自己没有写出来

后来和题解比较了一下，这几个地方写错了

把障碍物击碎后的状态，先改成0搜一遍，等搜完还要再改回1，是为了搜到以后的所有情况

找到起点后，把起点改成0

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 
 8 const int INF = 1000000000;
 9 int g[25][25];
10 int vis[25][25];
11 int n,m;
12 int sx,sy,ex,ey;
13 int flag,ans;
14 int dir[4][2] = {1,0,0,1,-1,0,0,-1};
15 
16 int in(int x,int y){
17     if(x >= 1 && x <= m && y >=1 && y <= n) return 1;
18     return 0;
19 }
20 
21 void dfs(int x,int y,int step){
22     if(step > 10) return;
23 
24     int i,xx,yy;
25     for( i = 0;i < 4;i++){
26          xx = x+dir[i][0];
27          yy = y+dir[i][1];
28          
29          if(step < ans && in(xx,yy) && g[xx][yy] != 1){
30              while(g[xx][yy] == 0 && in(xx,yy)){
31                  xx +=dir[i][0];
32                  yy +=dir[i][1];
33              }
34              int xx2 = xx-dir[i][0];
35              int yy2 = yy-dir[i][1];
36              if(in(xx,yy)){
37                  if(g[xx][yy] == 3){
38                      ans = step+1;
39                      return;
40                  }
41                  if(g[xx][yy] == 1){
42                      g[xx][yy] = 0;//碰到障碍物，将障碍物清除 
43                      dfs(xx2,yy2,step+1);
44                      g[xx][yy] = 1;//这一次dfs完后改回来是为了遍历完以后的所有情况 
45                  }
46              }
47          }
48     }
49 }
50 
51 int main(){
52     while(scanf("%d %d",&n,&m) != EOF && (m+n)){//输入的是n行m列 
53         memset(g,0,sizeof(g));
54         for(int i = 1;i <= m;i++){
55             for(int j = 1;j <= n;j++){
56                 scanf("%d",&g[i][j]);
57                 if(g[i][j] == 2) {
58                     sx = i,sy = j;
59                     g[i][j] = 0;
60                 }
61             }    
62         }
63 
64         ans = 12;
65         dfs(sx,sy,0);
66         if(ans > 10) printf("-1
");
67         else printf("%d
",ans);
68     }
69     return 0;
70 }

View Code

poj 1321

给出棋盘，旗子摆放不能同行或者同列，问放k个有多少种办法

感觉和poj 1564有一点点像，搜行，看对应的列是否被占用

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 typedef long long LL;
 8 char g[15][15];
 9 int vis[15];
10 LL ans;
11 int n,k;
12 
13 void dfs(int x,int cnt){
14     if(cnt == k){
15         ans++;
16     //    printf("ans = %d
",ans);
17         return;
18     }
19     for(int i = x;i <= n;i++){
20         for(int j = 1;j <= n;j++){
21             if(g[i][j] == '#' && !vis[j]){
22                 vis[j] = 1;
23                 dfs(i+1,cnt+1);
24                 vis[j] = 0;
25             }
26         }
27     }
28 }
29 
30 int main(){
31     while(scanf("%d %d",&n,&k) != EOF){
32         if(n == -1 && k == -1) break;
33         for(int i = 1;i <= n;i++)
34          for(int j = 1;j <= n;j++) cin>>g[i][j];
35          
36          ans = 0;
37          dfs(1,0);
38          printf("%I64d
",ans);
39     }
40     return  0;
41 }

View Code

uva 11396

给出一个无向图，再给出一个爪形，问这个无向图是否能够分成一个个爪形的单元

判断是否是二分图

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 
 8 const int maxn = 505;
 9 vector<int> g[maxn];
10 int color[maxn];
11 int n;
12 
13 bool bipartite(int u){
14     for(int i = 0;i < g[u].size();i++){
15         int v = g[u][i];
16         if(color[v] == color[u]) return false;
17         if(!color[v]) {
18             color[v] = 3-color[u];
19             if(!bipartite(v)) return false;
20         }
21     }
22     return true;
23 }
24 
25 int main(){
26     int u,v;
27     while(scanf("%d",&n) != EOF && n){
28         for(int i = 1;i <= n;i++) g[i].clear();
29         while(scanf("%d %d",&u,&v) != EOF){
30             if(u == 0 && v == 0) break;
31             g[u].push_back(v);g[v].push_back(u);
32         }
33         memset(color,0,sizeof(color));
34         color[1] = 1;
35         if(bipartite(1)) puts("YES");
36         else puts("NO");
37     }
38     return 0;
39 }

View Code