先上题目：

# [USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins

# 题目描述

农民 John 以拥有世界上最健康的奶牛为傲。他知道每种饲料中所包含的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛，以保持它们的健康，使喂给牛的饲料的种数最少。

给出牛所需的最低的维他命量，输出喂给牛需要哪些种类的饲料，且所需的饲料剂量最少。

维他命量以整数表示，每种饲料最多只能对牛使用一次，数据保证存在解。

# 输入格式

第一行一个整数 $v$ ，表示需要的维他命的种类数。
第二行 $v$ 个整数，表示牛每天需要的每种维他命的最小量。

第三行一个整数 $g$ ，表示可用来喂牛的饲料的种数。
下面 $g$ 行，第 $n$ 行表示编号为 $n$ 饲料包含的各种维他命的量的多少。

# 输出格式

输出文件只有一行，包括牛必需的最小的饲料种数 $p$ ；后面有 $p$ 个数，表示所选择的饲料编号（按从小到大排列）。

如果有多个解，输出饲料序号最小的（即字典序最小）。

# 样例 #1

# 样例输入 #1

4
100 200 300 400
3
50  50  50  50
200 300 200 300
900 150 389 399

# 样例输出 #1

2 1 3

# 提示

【数据范围】
对于 $100\%$ 的数据， $1\le v \le 25$ ， $1\le g \le 15$ 。
输入的所有整数在 $[1,1000]$ 范围内。

USACO 2.1

翻译来自 NOCOW

# 题解

太长时间没有刷题，一些简单的深搜也不太会写了。这题不用剪枝直接暴力即可。
每个饲料只有 0，1 两种状态（要或者不要）
然后 search (t,s)
t 代表选中的饲料，s 代表选中饲料的个数，要么 search (t+1,s) 当前饲料不选，要么 search (t+1,s+1)
选当前饲料，数据量小直接就能 AC

#include <bits/stdc++.h> //懒人最爱的万能头文件 
using namespace std;//名字空间 
int ans[1000];//这个数组是来存储解的。 
int a[1000];//表示牛每天需要的每种维他命的最小量。 
int b[1000][1000];//每种饲料包含的各种维他命的量的多少。
int c[1000];//每次搜索选的饲料编号 
int n,m,minn=100000000;
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 search(int t,int 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放在数组里
	search(t+1,s+1);//搜索一步
	c[s+1]=0;//回溯一步
	search(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];//还是读入
	}
	search(1,0);//调用搜索函数
	cout<<minn<<' ';//输出
	for(int i=1; i<=minn; i++)
	cout<<ans[i]<<' ';//还是输出
	return 0;//结束程序
}

写这个主要是因为第一眼还是 dx，dy 类型的深搜，刚开始手足无措没有想到如何处理这种 0，1 状态的深搜使其能搜索所有的状态。

下面再贴一道纯模板题

# 深さ優先探索

# 题面翻译

高桥先生住的小区是长方形的，被划分成一个个格子。高桥先生想从家里去鱼店，高桥先生每次可以走到他前后左右四个格子中的其中一个，但不能斜着走，也不能走出小区。

现在给出地图：


```g```：代表鱼店

```.```：代表道路

```#```：代表墙壁

高桥先生不能穿过墙壁。

输入：第一行输入n(1<=n<=500),m(1<=m<=500)代表小区的长和宽，接下来n行每行m个字符，描述小区中的每个格子。

输出：如果高桥先生能到达鱼店，输出"Yes"，否则输出"No"。

## 题目描述

[problemUrl]: https://atcoder.jp/contests/atc001/tasks/dfs_a

この問題は、講座用問題です。ページ下部に解説が掲載されています。

高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。 長方形の各辺は東西及び南北に並行です。 各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。 また、塀の区画は通ることができません。

高橋君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。

## 输入格式

入力は以下の形式で標準入力から与えられる。

> $ H $ $ W $ $ c_{0,0} $ $ c_{0,1} $ $ c_{0,W-1} $ $ c_{1,0} $ $ c_{1,1} $ $ c_{1,W-1} $ : $ c_{H-1,0} $ $ c_{H-1,1} $ $ c_{H-1,W-1} $

- $ 1 $ 行目には、街の南北の長さとして整数 $ H(1≦H≦500) $ と東西の長さとして整数 $ W(1≦W≦500) $ が空白で区切られて与えられる。
- $ 2 $ 行目からの $ H $ 行には、格子状の街の各区画における状態 $ c_{i,j}(0≦i≦H-1,\ 0≦j≦W-1) $ が与えられる。 
  - $ i $ 行目 $ j $ 文字目の文字 $ c_{i,j} $ はそれぞれ `s`, `g`, `.`, `#` のいずれかで与えられ、座標 $ (j,i) $ が下記のような状態であることを表す。 
      - `s` : その区画が家であることを表す。
      - `g` : その区画が魚屋であることを表す。
      - `.` : その区画が道であることを表す。
      - `#` : その区画が塀であることを表す。
  - 高橋君は家・魚屋・道は通ることができるが、塀は通ることができない。
  - 与えられた街の外を通ることはできない。
  - `s` と `g` はそれぞれ 1 つずつ与えられる。

## 输出格式

塀を $ 1 $ 回も壊さずに、家から魚屋まで辿り着くことができる場合は `Yes`、辿りつけない場合は `No` を標準出力に $ 1 $ 行で出力せよ。




## 题解

这道题就纯是最常见也是最简单的DFS了，多了一个字符串的转换，这里也可以复习一下getchar()函数和cin和scanf函数，

>**cin从第一个非空格、非回车、非tab键的位置开始读取，当与所要读取类型一致时则开始读取，遇上空格、tab键不再读取、回车结束。**

>输入缓冲区有数据：从输入缓冲区读取，从非空字符开始，遇到空格结束(回车、空格、tab)。尾回车会被留在输入缓冲区，并且不做处理。
  输入缓冲区没有数据：获取键盘输入，当按下回车的时候，输入的数据连同刚按下的回车符被送入输入缓冲区。然后从输入缓冲区区读取数据，规则和上面标黄部分一样。

>1、scanf从非空格字符开始读取，空格字符结束(空格、TAB、回车)
   2、当缓冲区没有数据的时候，需要先从键盘输入，然后放入缓冲区再读取。
   3、当缓冲区有数据的时候不会从键盘获取数据。我们可以从上面输入看到第二个sacnf并没有从键盘获取数据
   4、sacnf会把末尾回车留在缓冲区，给以后的输入埋雷

接着贴上代码

```cpp
#include<bits/stdc++.h>
using namespace std;
int map1[502][502];
int record[502][502];
#define xx x+dx[i]
#define yy y+dy[i]
int sx,sy,fx,fy;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m;
int flag=0;
void dfs(int x,int y){
	record[x][y]=1;
	if(x==fx&&y==fy){
		flag=1;
		return;
	}
	if(!flag)
		for(int i=0;i<4;i++){
			if(xx<=n&&x>0&&y<=m&&y>0&&map1[xx][yy]==0&&record[xx][yy]==0){
				dfs(xx,yy);
			}
		}
	return;
}

int main(){
	cin>>n>>m;
	getchar();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char tmp;
			tmp = getchar();
			if(tmp=='s'){
				sx = i,sy = j;
				map1[i][j]=0;
			}
			else if(tmp == '#'){
				map1[i][j]=1;
			}
			else if(tmp == 'g'){
				fx=i,fy=j;
			}
			else{
				map1[i][j] = 0;
			}
		}
		getchar();
	}
	dfs(sx,sy);
	if(flag){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
	return 0;
}

再上一题 dfs，其实这一题和放的第一题是同一种类型，或者说是第一和第二的结合，在二维数组中每个元组有选和不选两种状态，这时候应该的做法。
先上题目：

# 取数游戏

# 题目描述

一个 $N\times M$ 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻 $8$ 个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少。

# 输入格式

第一行有一个正整数 $T$ ，表示了有 $T$ 组数据。

对于每一组数据，第一行有两个正整数 $N$ 和 $M$ ，表示了数字矩阵为 $N$ 行 $M$ 列。

接下来 $N$ 行，每行 $M$ 个非负整数，描述了这个数字矩阵。

# 题解

这里不给出样例输入输出了
因为数据量小，直接暴力深搜。

#include<iostream>
#include<string.h>
using namespace std;
int T;
int N,M;
int map[9][9];
int maxsum = 0;
int enable[8][8];
int dx[8]={0,0,1,1,1,-1,-1,-1};
int dy[8]={1,-1,0,1,-1,1,0,-1};
int currentsum = 0;
#define xx x+dx[i]
#define yy y+dy[i]

void search(int x,int y)
{
	if(y == M+1){
		search(x+1,1);
		return;
	}
	if(x == N+1){
		maxsum = max(maxsum,currentsum);
		return;
	}
	
	search(x,y+1);
	if(enable[x][y]==0){
		currentsum += map[x][y];
		for(int i=0;i<8;i++){
			enable[xx][yy]++;
		}
		
		search(x,y+1);
		
		for(int i=0;i<8;i++){
			enable[xx][yy]--;
		}
		currentsum-=map[x][y];		 
	}
}

int main()
{
	cin>>T;
	for(int i=1;i<=T;i++){
//		memset(enable,0,sizeof(enable));
//		memset(map,0,sizeof(map));//在做每个数据前都要初始化数组 
		cin>>N>>M;
		maxsum = 0;
		for(int j=1;j<=N;j++){
			for(int k=1;k<=M;k++){
				cin>>map[j][k];
			}
		}
		currentsum=0;
		search(1,1);
		cout<<maxsum<<endl;
	}
	
	
	return 0;
 }

这里我第一次写代码时，并没有考虑到所有的情况，向上面这样写才能考虑到所有的情况，因为你需要考虑到每个元组选或不选，要在 search 中体现出来。而我第一次写代码时默认都选择，进行了 n*m 的循环寻找，自然会少一些情况。这算是本题的一点收获。

# 题目描述

给出一个 $N$ 个顶点 $M$ 条边的无向无权图，顶点编号为 $1\sim N$ 。问从顶点 $1$ 开始，到其他每个点的最短路有几条。

# 输入格式

第一行包含 $2$ 个正整数 $N,M$ ，为图的顶点数与边数。

接下来 $M$ 行，每行 $2$ 个正整数 $x,y$ ，表示有一条由顶点 $x$ 连向顶点 $y$ 的边，请注意可能有自环与重边。

# 输出格式

共 $N$ 行，每行一个非负整数，第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 $ ans \bmod 100003$ 后的结果即可。如果无法到达顶点 $i$ 则输出 $0$ 。

# 样例 #1

# 样例输入 #1

# 样例输出 #1

# 提示

$1$ 到 $5$ 的最短路有 $4$ 条，分别为 $2$ 条 $1\to 2\to 4\to 5$ 和 $2$ 条 $1\to 3\to 4\to 5$ （由于 $4\to 5$ 的边有 $2$ 条）。

对于 $20\%$ 的数据， $1\le N \le 100$ ；
对于 $60\%$ 的数据， $1\le N \le 10^3$ ；
对于 $100\%$ 的数据， $1\le N\le10^6$ ， $1\le M\le 2\times 10^6$ 。