title: ACM-DFS-Practice
tags:

  • ACM
  • DFS
    abbrlink: 7a871ff6
    date: 2020-11-17 17:53:56

部分和问题

给定整数a1,a2…,an,判断是否可以从中选出若干数，使他们的和恰好为k

  1. #include<iostream>
  2. #include<cstdio>
  4. using namespace std;
  6. const int maxn=20 + 5;
  8. int a[maxn],n,k;
  10. bool dfs(int i,int sum)
  11. {
  12.     if(i==n)    return sum == k;
  13.     if(dfs(i+1, sum))   return true;
  14.     if(dfs(i+1, sum+a[i]))  return true;
  15.     return false;
  16. }
  18. int main(){
  19.     cin>>n;
  20.     for(int i=0;i<n;i++)
  21.     {
  22.         cin>>a[i];
  23.     }
  24.     cin>>k;
  25.     if(dfs(0,0))    cout<<"Yes"<<endl;
  26.     else cout<<"No"<<endl;
  27.     return 0;
  28. }

Lake Counting(POJ2386)

  1. #include<iostream>
  2. #include<cstdio>
  4. using namespace std;
  6. const int maxn = 100 + 5;
  8. int N,M;
  9. char f[maxn][maxn];
  11. void dfs(int x, int y)
  12. {
  13.     f[x][y]='.';
  14.     for(int dx=-1;dx<=1;dx++)
  15.         for(int dy=-1;dy<=1;dy++)
  16.         {
  17.             int nx=x+dx, ny=y+dy;
  18.             if(0 <= nx && nx < N && 0<=ny && ny< M && f[nx][ny]=='W')
  19.                 dfs(nx,ny);
  20.         }
  21.     return;
  22. }
  24. void solve()
  25. {
  26.     int res=0;
  27.     for(int i=0;i<N;i++)
  28.     {
  29.         for(int j=0;j<M;j++)
  30.         {
  31.             if(f[i][j]=='W')
  32.             {
  33.                 dfs(i, j);
  34.                 res++;
  35.             }
  36.         }
  37.     }
  38.     cout<<res<<endl;
  39. }
  41. int main(){
  42.     cin>>N>>M;
  43.     for(int i=0;i<N;i++)
  44.         for(int j=0;j<M;j++)
  45.             cin>>f[i][j];
  46.     solve();
  47.     return 1;
  48. }