【dfs思想】一直往深处走，直到找到解或者走不下去为止；
dfs(dep,...) //dep代表目前dfs的深度
{if(找到解||走不下去了){...return ;}枚举下一种情况，dfs(dep+1,...)
}1209: 最大面积
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 139 Solved: 55
[Submit][Status][Web Board]Description
给定一个n*m的矩阵，其中有k个格子是1，其他全部是0。
你的任务是告诉我最大的全部由1组成的图形的最大面积为多少？
Input
输入包括多组测试数据，第一行为三个正整数n,m,k，(1<=n,m<=100,1<=k<=n*m)，接下来k行，每行有两个正整数x,y(1<=x<=n,1<=y<=m)代表格子(x,y)是1。
Output
对于每组测试数据，输出最大的面积。
Sample Input
3 4 5 3 2 2 2 3 1 2 3 1 1
Sample Output
4
HINT
Source
xzy
【分析】深搜。
【代码】
#include<bits/stdc++.h>
using namespace std;
int a[105][105];
int ans;
void dfs(int x,int y)
{a[x][y]=0;//cout<<x<<","<<y<<endl;if(a[x+1][y]==1)ans++,dfs(x+1,y);if(a[x-1][y]==1)ans++,dfs(x-1,y);if(a[x][y+1]==1)ans++,dfs(x,y+1);if(a[x][y-1]==1)ans++,dfs(x,y-1);
}
int main()
{int n,m,k,x,y;while(~scanf("%d%d%d",&n,&m,&k)){ans=0;memset(a,0,sizeof(a));for(int i=1;i<=k;i++){scanf("%d%d",&x,&y);a[x][y]=1;}int maxx=-1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(a[i][j]==1)dfs(i,j),ans++;maxx=max(maxx,ans);ans=0;} cout<<maxx<<endl;}return 0;
}1711: 背包
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 227 Solved: 115
[Submit][Status][Web Board]Description
你有一个神奇的背包，他的容积是m(0<m<=80)，只有你装满他，你才能拿走他，现在给你n(1<=n<=20)个物品Xi(Xi<=m)，那么一共有几种方式，可以让你拿走背包？
Input
第一行 n,m
第二行 n个数字
Output
输出方案数
Sample Input
3 40
20 20 20
Sample Output
3
【分析】dfs简单应用。注意要两次递归。
【代码】
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,ans=0;
int a[25];
void dfs(int v,int k)
{if(v==0){ans++;return;}if(v<0||k>n)return;dfs(v-a[k],k+1);dfs(v,k+1);//以这个容量开始装入k+1的东西
}
int main()
{while(~scanf("%d%d",&n,&m)){for(int i=1;i<=n;i++)scanf("%d",&a[i]);ans=0;dfs(m,1);printf("%d\n",ans);}return 0;
}