周笔记总结4.17

这周继续学习了数据结构的内容，但这周主要看的还是DFS，BFS的题解和博客，这周看了大概有六十多篇博客，还有很多道题解，其中大部分都是在周六看的，其实很多题的类型是一样的。

P1019 [NOIP2000 提高组] 单词接龙 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1019这道题只看题目就感觉很难，刚开始就字符拼接这块写了一大堆，写完搜索不会写了，光找两个字符串的最小重叠部分就写了好多，最后写不下去了，需要太多代码了，于是就去找大佬题解了，确实自己写繁了，梳理一下大佬的思路吧。

对所有的字符串循环，对于首字母符合条件的以这个字符串开头进行搜索，所以可能搜索不止一次。

由于每个字符串最多出现2次，所以用一个标记数组记录某个字符串的使用次数，2次之后就不再使用。

在搜索函数里，难点在于最小重叠部分的寻找，大佬使用了string的成员函数substr，他可以截取字符串的一部分，单参数截取该位置到尾的字符串，双参数前一部分是截取位置，后一部分是截取长度。

由于只需要求出最小重叠部分（因为最小重叠才能确保最大长度），所以从上一个字符串的尾部和当前字符串的头部开始检测，如果截取的字符串相等，那就可以拼接，继续下一步搜索。

P1460 [USACO2.1]健康的荷斯坦奶牛 Healthy Holsteins - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1460这道题目还是一个两路搜索，对于每种饲料，都可以选择加或者不加。

同时还需要设置visit数组来保存访问路径。

每访问后需要对此时的状态进行判定，是否满足条件，满足条件则返回并对比答案来确定是否要更新答案，不满足条件继续向下搜索。

#include
using namespace std;
int Vitamin[30][30] = { 0 }, Need[30] = { 0 };
//两个数组分别是饲料各维他命含量，牛所需维他命量
int visit[30] = { 0 }, Anvisit[30] = { 0 }, ans = 5000;
//visit用来存放当前饲料编号，Anvisit存放答案的饲料编号
//ans存放答案数量，初始值为一个比较大的数
int v = 0, g = 0;
//v,g含义题目中有，不赘述
bool Judge(int amount)
{
	//该函数用来判断当前情况下是否已满足需求
	//amount是已投喂的饲料总数
	if (!amount)return false;
	//如果一种饲料都没加直接pass
	for (int i = 1; i <= v; i++)
	{
		int sum = 0;
		for (int j = 1; j <= amount; j++)
			sum += Vitamin[visit[j]][i];
		//累加，算出每种维生素的含量
		if (sum < Need[i])return false;
		//一旦出现有一种含量小于需求的直接false
	}
	return true;
}
void DFS(int number,int count)
{
	//number为饲料编号，count为饲料总数
	//这样设置参数可以很大程度上避免思考得过于复杂
	if (number > g)
		return;
	//边界
	if (Judge(count)) {//如果满足条件
		if (count < ans) {//并且新答案比原答案小
			ans = count;
			for (int i = 1; i <= count; i++)
				Anvisit[i] = visit[i];
			//更新答案
		}
		return;
		//使命完成，直接返回，不需要再向下执行
	}
	visit[count + 1] = number + 1;
	//准备访问，先打标记
	DFS(number + 1, count + 1);
	//访问下一种饲料并加入
	visit[count + 1] = 0;
	//访问结束，消除标记
	DFS(number + 1, count);
	//访问下一种饲料但不加入
}
int main(void)
{
	scanf("%d", &v);
	for (int i = 1; i <= v; i++)
		scanf("%d", &Need[i]);
	scanf("%d", &g);
	for (int i = 1; i <= g; i++)
		for (int j = 1; j <= v; j++)
			scanf("%d", &Vitamin[i][j]);
	//一堆输入
	DFS(0, 0);
	//注意从编号零开始搜索，因为编号一也要搜索加或者不加两条路
	printf("%d", ans);
	for (int i = 1; i <= ans; i++)
		printf(" %d", Anvisit[i]);
	return 0;
}

P1451 求细胞数量 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1451
本体考虑用DFS解决问题时，发现了两个之前并没在意的错因，第一个便是在编写搜索函数时，对于搜索的条件并没有设置，导致没有编译通过，程序报错，以本题为例，递归终止条件自然不用多说，即是否越界，而搜索之前，须先判断当前位置是否为细胞数字，是的话，才去搜索，否则不搜；前几次编译的时候，就因为没有设置该条件，导致程序无法运行，直接终止了。

第二个便是一直忽略的错误，比如去枚举搜索四个方向时，注意观察一下两个程序的区别，此处细节直接决定成败！
方向1：（程序错误展示)
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void DFS(int x,int y)
{
if(x<1||x>n||y<1||y>m) return ;
a[x][y]=0;
for(int i=0;i<4;i++)
{
x=x+dx[i],y=y+dy[i];
if(a[x][y]!=0) DFS(x,y); //符合条件的去搜，否则不搜;
}
}
运行程序发现，编译不通过！！！！错误，以下正解;

 void DFS(int x,int y)
   {
       if(x<1||x>n||ym)   return ;
       a[x][y]=0;
       for(int i=0;i<4;i++)
       {
           int xx=x+dx[i],yy=y+dy[i];
           if(a[xx][yy])   DFS(xx,yy);
          }
        }

本周学到了很多，通过做过的题目也是感觉自己的能力又提高了一点，其中还是，思路是最重要的，然后把具体思路分成几个函数去完成，所以更是有成百上千种做法，所以当我做这些题的时候，也会觉得这道题我写的太麻烦了，很多都没有必要，以后如果想提高自己，那就必须要寻找最优解，使程序看起来更加的完美简洁。

希望通过以后的学习，慢慢提高自己，实现这门课的真正价值。