DFS例题

DFS例题：

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

限制条件：

1<=n<=20

-10⁸<=ai | k<=10⁸

 1 #include<cstdio>
 2 using namespace std;
 3 int k,n;
 4 //已经从前i项得到了部分和temp，然后对i之后的项进行分支 
 5 bool DFS(int a[],int temp,int i){
 6     if(i==n) return temp==k;//前n项都计算过了，返回temp是否与k相等 
 7     if(DFS(a,temp,i+1)) return true;//不加上a[i]的情况 
 8     if(DFS(a,temp+a[i],i+1)) return true;//加上a[i]的情况 
 9     return false;//无论是否加上a[i]都凑不成k就返回false 
10 }
11 int main(){
12     scanf("%d%d",&n,&k);
13     int b[n];
14     for(int i=0;i<n;i++){
15         scanf("%d",&b[i]);
16     }
17     if(DFS(b,0,0))printf("Yes");
18     else printf("No");
19     return 0;

【POJ2386】Lake Counting
   有一个大小为M*N的园子，雨后积起了水。八连通的积水被认为是连接在一起的。请求出园子里共有多少水洼？（八连通指的是下面图中相对W的*的部分）
   ***
   *W*
   ***
   限制条件：
   N,M≤100

   输入

   第一行包含两个正整数 N 和 M，表示将一个园子地面分成N*M块方格，N 行，M列，接下来的 N 行描述了园子地面状况，其中‘W’表示积水的水洼，‘.’表示没有积水。1 <= N <= 100; 1 <= M <= 100

   输出

   仅一个数，表示水洼的总数。

   输入示例

   10 12
   w........ww.
   .www.....www
   ....ww...ww.
   .........ww.
   .........w..
   ..w......w..
   .w.w.....ww.
   w.w.w.....w.
   .w.w......w.
   ..w.......w.

输出示例
3

思路：

DFS：

从矩阵中w开始，将该w和与它八连通的w都换成 . ，每次做这样的处理就count一次。

 1 include<cstdio>
 2 #include<iostream>
 3 #define MAX 110
 4 using namespace std;
 5 int n,m;
 6 char b[MAX][MAX];
 7 void DFS(int x,int y){
 8     b[x][y]='.';
 9     for(int dx=-1;dx<=1;dx++){
10         for(int dy=-1;dy<=1;dy++){
11             int nx=x+dx,ny=y+dy;
12             if(0<=nx&&0<=ny&&nx<n&&ny<m&&b[nx][ny]=='w') {
13                 DFS(nx,ny);
14             }
15         }
16     }
17     return ;
18 }
19 int main(){
20     scanf("%d%d",&n,&m);
21     for(int i=0;i<n;i++){
22         for(int j=0;j<m;j++){
23             //scanf("%c",&b[i][j]);
24             cin>>b[i][j];
25         }
26     }
27     int count=0;
28     for(int i=0;i<n;i++){
29         for(int j=0;j<m;j++){
30             if(b[i][j]=='w') {
31                 DFS(i,j);count++;
32             }
33         }
34     }
35     //printf("%c",b[0][0]);
36     printf("%d",count);
37     //cout<<b[0][0];
38     return 0;
39 }

总结：输入时，用scanf会快，但是它读入回车，因此不能有回车的输入，因此按照题目的输入方式就会不正确。最后用的标准输入cin。