1.P1460 [USACO2.1]健康的荷斯坦奶牛 Healthy Holsteins
农民 John 以拥有世界上最健康的奶牛为傲。他知道每种饲料中所包含的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛，以保持它们的健康，
使喂给牛的饲料的种数最少。
给出牛所需的最低的维他命量，输出喂给牛需要哪些种类的饲料，且所需的饲料剂量最少。
维他命量以整数表示，每种饲料最多只能对牛使用一次，数据保证存在解。
输入格式
第一行一个整数v,表示需要的维他命的种类数。
第二行v个整数，表示牛每天需要的每种维他命的最小量。
第三行一个整数g,表示可用来喂牛的饲料的种数。
下面g行，第n行表示编号为n饲料包含的各种维他命的量的多少。
输出格式
输出文件只有一行，包括牛必需的最小的饲料种数p;后面有 p个数，表示所选择的饲料编号（按从小到大排列）。
如果有多个解，输出饲料序号最小的（即字典序最小）。
下附代码(注释较长，请放大查看)
#include<bits/stdc++.h>
using namespace std;
int ans[1000];//存储解的数组
int a[1000];//表示牛每天需要的每种维他命的最小量(便于输入第二行的v个整数)
int b[1000][1000];//每种饲料包含的各种维他命的量的多少(用二维数组的原因是有饲料种数和维他命的量这两个变量，用到二重循环)
int c[1000];//每次搜索选的饲料编号
int n,m,minn=100000000;//n指表示需要的维他命的种类数，m指可用来喂牛的饲料的种数，minn表示"暂时的最优解"
bool pd(int x)/*这是判断每次选的那些饲料中的维生素之和是不是都大于等于牛每天需要的每种维他命的最小量的函数*/
{
for(int i=1; i<=n; i++)
{
int sum=0;
for(int j=1; j<=x; j++)
sum+=b[c[j]][i];//用一个sum累加
if(sum<a[i]) return false;//如果有一项维生素比牛需要的维生素要少，直接返回false
}
return true;
}
void dfs(int t,int s)//搜索的函数，t表示搜索到了第t种饲料，s表示目前选的饲料的总数。
{
if(t>m)//搜索超出边界了，搜索到的饲料数大于可用来喂牛的饲料数
{
if(pd(s))/*必须得满足条件:每次选的那些饲料中的维生素之和都大于等于牛每天需要的每种维他命的最小量*/
{
if(s<minn)//判断选的饲料的总数小于以前的最优解
{
minn=s;//替换掉
for(int i=1; i<=minn; i++)
{
ans[i]=c[i];//答案的数组也要被替换
}
}
}
return; //返回
}
c[s+1]=t;//把t放在数组里
dfs(t+1,s+1);//搜索一步
c[s+1]=0;//回溯一步
dfs(t+1,s);//如果不选第t种饲料的操作
}
int main()//主函数部分
{
cin>>n;//读入
for(int i=1;i<=n;i++)
cin>>a[i];//读入
cin>>m;//读入
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
cin>>b[i][j];//还是读入
}
dfs(1,0);//调用搜索函数
cout<<minn<<" ";//输出
for(int i=1; i<=minn; i++)
cout<<ans[i]<<" ";//输出
return 0;
}
/*总结：首先定义一个搜索函数，函数传递的变量为t和s,t表示搜索到了第t种饲料，s表示目前选的饲料的总数。
然后确定搜索的边界，也就是t>饲料的种数，然后判断每次选的那些饲料中的维生素之和是不是都大于等于牛每天需要的每种维他命的最小量（可以用个函数写）。如果是，就判断选的饲料的总数小于以前的最优解，如果小于，那么当前最优解就要被替换掉，而最优解的一个数组也要被替换掉。最后return即可。2.洛谷 P1596 湖的统计
题目描述
由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个NxM(1<=N<=100;1<=M<=100)网格图表示。每个网格中有水(‘W’) 或是旱地(‘.’)。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。
输入格式
第1行：两个空格隔开的整数：N 和 M 第2行到第N+1行：每行M个字符，每个字符是’W’或’.’，它们表示网格图中的一排。字符之间没有空格。
输出格式
一行：水坑的数量
下附代码:
#include<bits/stdc++.h>
using namespace std;
char wl[1001][1010];//这个数组用来存储水塘(water)和陆地(land)
int i,j,m,n,sum=0;
void dfs(int a,int b)
{
if (wl[a][b]=='W')//如果是水塘，就把它变成陆地，并且搜索四周的水塘，这样就可以把一片水塘找出
{
wl[a][b]='.';//变成陆地
dfs(a-1,b-1);
dfs(a-1,b);
dfs(a-1,b+1);
dfs(a,b-1);
dfs(a,b+1);
dfs(a+1,b-1);
dfs(a+1,b);
dfs(a+1,b+1);//这八行是递推，转一圈
return;
}
}
int main()
{
cin>>m>>n;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
cin>>wl[i][j];//输入
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(wl[i][j]=='W')//如果有水塘，计数器+1，并且将这个水塘从我们的搜索过程中排除
{
dfs(i,j);
sum++;
}
}
cout<<sum;
return 0;
}
3.P1451 求细胞数量
题目描述
一矩形阵列由数字0到9组成，数字1到9代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。
输入格式
第一行两个整数代表矩阵大小n和m。
接下来n行，每行一个长度为m的只含字符
0
到
9
的字符串，代表这个n×m 的矩阵。
(n为行，m为列)
输出格式
一行一个整数代表细胞个数。
下附代码:
#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[101][101];
int ans=0;
void dfs(int x,int y)
{ if(x<1||y<1||x>n||y>m)
return;//边界
//以下是四个点的判断(顺序随便)
//只要不是0都变成0，然后继续搜索
if(a[x][y+1]!='0')
{
a[x][y+1]='0';
dfs(x,y+1);
}
if(a[x][y-1]!='0')
{
a[x][y-1]='0';
dfs(x,y-1);
}
if(a[x+1][y]!='0')
{
a[x+1][y]='0';
dfs(x+1,y);
}
if(a[x-1][y]!='0')
{
a[x-1][y]='0';
dfs(x-1,y);
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin>>a[i][j];
//用字符数组输入，因为没有空格
}
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(a[i][j]!='0') {
a[i][j]=0;//不是0就变成零
ans++;
dfs(i,j);
//目的是将所有这个细胞中的元素清零
//这样就可以直接找下一个细胞的某个元素
}
}
}
printf("%d",ans);
return 0;
}
/*注意:a是char类型，a[i][j]！=0是错误的，应该写成a[i][j]!='0'！！！
(本人WA了十次，花了10分钟才找到)*/
4.P6183 [USACO10MAR] The Rock Game S
题目描述
在奶牛回家休息和娱乐之前，Farmer John 希望它们通过玩游戏获得一些智力上的刺激。游戏板由n个相同的孔组成，这些孔最初
都是空的
。一头母牛要么用石头盖住一个洞，要么揭开一个先前被盖住的洞。
游戏状态
的定义是哪些洞被石头覆盖，哪些洞没有覆盖。游戏的目标是让奶牛准确地到达每个可能的游戏状态一次，然后返回到所有洞都没有覆盖的状态。以下是他们其中一次游戏的示例（空的洞用
O
表示，用石头盖住的洞用
X
表示）：
| 时间 | 洞 1 | 洞 2 | 洞 3 | 描述 |
|---|---|---|---|---|
| 0 | O | O | O | 一开始所有的洞都是空的 |
| 1 | O | O | X | 盖上洞 3 |
| 2 | X | O | X | 盖上洞 1 |
| 3 | X | O | O | 打开洞 3 |
| 4 | X | X | O | 盖上洞 2 |
| 5 | O | X | O | 打开洞 1 |
| 6 | O | X | X | 盖上洞 3 |
| 7 | X | X | X | 盖上洞 1 |
现在牛被卡住玩不下去了！他们必须打开一个洞，不管他们打开哪个洞，他们都会到达一个他们已经到达的状态。例如，如果他们从第二个洞中取出岩石，他们将到达他们在时间 22 已经访问过的状态（
X O X
）。
下面是一个 3 个孔的有效解决方案：
| 时间 | 洞 1 | 洞 2 | 洞 3 | 描述 |
|---|---|---|---|---|
| 0 | O | O | O | 一开始所有的洞都是空的 |
| 1 | O | X | O | 盖上洞 2 |
| 2 | O | X | X | 盖上洞 3 |
| 3 | O | O | X | 打开洞 2 |
| 4 | X | O | X | 盖上洞 1 |
| 5 | X | X | X | 盖上洞 2 |
| 6 | X | X | O | 打开洞 3 |
| 7 | X | O | O | 打开洞 2 |
| 8 | O | O | O | 打开洞 1，恢复到原来的状态 |
现在，奶牛们厌倦了这个游戏，它们想找你帮忙。
给定 n，求游戏的有效解决方案序列。如果有多个解决方案，则返回
任意一个
。
输入格式
仅一行，一个整数 n。
输出格式
共 n行，每行一个长度为 n 的字符串，其中只包含字符
O
和
X
，该行中的第 ii 个字符表示第 ii 个孔在此状态下是被覆盖还是未覆盖，第一行和最后一行必须全部都是
O
。
对于 100% 的数据，有1≤n≤15。
(此题采用special judge)
(这年头奶牛也会玩游戏了)
下附代码:
#include<bits/stdc++.h>
using namespace std;
int n;
int a[20];//记O为0，X为1
int vis[1<<20];
int ans[1<<20][20],tot=0;
void output(){//输出函数
for(int i=1;i<=1<<n;i++){
for(int j=1;j<=n;j++){
cout<<(ans[i][j]?'X':'O');//三目运算符的使用
}
cout<<endl;
}
}
int calc(){//将一个二进制数转化为十进制数
int ans=0;
for(int i=1;i<=n;i++){
ans=ans*2+a[i];//常规操作
}
return ans;
}
void dfs(int pos)//pos==position
{
if(pos==(1<<n))
{//因为ans初始化时OOOOO...OO，所以最后留一组输出即可
output();//输出
exit(0);//special judge
}
for(int i=1;i<=n;i++)
{
a[i]=!a[i];//一位差别
if(vis[calc()]){//走过了
a[i]=!a[i];//还原,两个!还原
continue;//再见
}
vis[calc()]=true;//记录，走过了
for(int j=1;j<=n;j++){
ans[pos][j]=a[j];//存储答案
}
dfs(pos+1);//继续搜索下一个
vis[calc()]=false;//回溯，再次标为“未来过”
a[i]=!a[i];
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cout<<'O';//输出
cout<<endl;
vis[0]=true;//OOO.OOO不可再走
dfs(1); //从1开始搜索
return 0;
}
5.P1506 拯救oibh总部
题目背景
oibh总部突然被水淹没了！现在需要你的救援……
题目描述
oibh被突来的洪水淹没了>.<还好oibh总部有在某些重要的地方起一些围墙，用*号表示，而一个封闭的*号区域洪水是进不去的……现在给出oibh的围墙建设图，问oibh总部没被淹到的重要区域（由”0″表示）有多少。
输入格式
第一行是两个数，x和y（x,y<=500）
第二行及以下是一个由*和0组成的x*y的图。
输出格式
输出没被水淹没的oibh总部的“0”的数量。
(oibh,Olympiad in Informatics Beginners’ Home,信息学初学者之家)
下附代码:
#include <bits/stdc++.h>
#define MAX 600
using namespace std;
int a[MAX][MAX];
int n, m, cnt = 0;//cnt记录答案
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
void dfs(int x, int y) {
if(x < 0 || y < 0 || x > n + 1 || y > m + 1 || a[x][y] == 1)//找边界
return;
a[x][y] = 1;
for(int i = 0; i < 4; i++) {
dfs(x + dx[i], y + dy[i]);
}
}
int main() {
cin>>n>>m;
char ch;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
cin>>ch;
if(ch == '*')
a[i][j] = 1;
else
a[i][j] = 0;
}
dfs(0, 0);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
if(a[i][j] == 0)
cnt++;
}
cout<<cnt;
return 0;
}