每日编程中遇到任何疑问、意见、建议请公众号留言或加入每日编程群聊739635399
有一个M*N的材料和一个s*t的模板，从材料中切除模板，求最大能切出来的模板的数量。
输入格式：
第一行 M N
下面的M行N列：材料的具体内容
s 和 t
下面的s行t列：模板材料的具体内容
输出格式：
最大能切出来的模板的数量
输入样例：
3 4a b c dc d a ba c c d2 2a bc d
输出样例：
2
解决方法：
（1）算法的基本思想：
1.定义两个字符数组将这两幅图存储起来;
2.使用一个判断模块，当进行搜索的时候，判断该位置是否合法(也就是以该位置为起点的s*t图形是否能和输入的s*t图形恰好匹配);3. 构造一个初始化模块，当位置合法的时候，可以选择使用或者不使用这种位置;
4.采用深度搜索方式，逐行进行扫描。 （1） 如果到某一位置，判断时合法。我们采取两种行动（要么将大图中匹配的位置标记为0，然后继续深度搜索，要么就当什么事都没有发生，继续逐行扫描）采取这两种操作的原因是，我们不知道哪种操作是更好的结果，所以我们就都试试；
（2）当该行扫描完之后，进入下一行继续进行扫描；
（3）程序出口是扫描到了最后一行；
（4）因为递归过程中遍历了所有的可能，如果遇到更优解，我们需要进行答案的更新。
（2）代码实现：
#include<iostream>#include<string.h>usingnamespacestd;#define MAX 100charmap[MAX][MAX], mapb[MAX][MAX];char temp[MAX][MAX]; //记录中间图的变换，方便在递归中的回溯进行使用int M, N, s, t; //分别为这两个图形的长和宽int Max, ans; //分别记录每次遍历的最大块儿数和最终答案booljudge(charmap[][MAX], int i, int j){int x = i;int y = j; //x来表示行数，y来表示列数for (i = 0; i < s; i++) //判断两个图是否匹配for (j = 0; j < t; j++)if (map[x + i][y + j] != mapb[i][j])returnfalse;returntrue;}//将已经遍历过的位置标记voidinit_temp(int x, int y){for (int i = 0; i < M; i++)for (int j = 0; j < N; j++) temp[i][j] = map[i][j];for (int i = 0; i < s; i++)for (int j = 0; j < t; j++) temp[x + i][y + j] = '0';}voiddfs(charmap[][MAX], int x, int y, int Max){if (ans < Max) //ans来记录块的数量 ans = Max;if (x >= M) { //记录递归出口,走到最后一行就返回return; }for (int i = y; i < N; i++) { //对x行的每一列都进行搜索if (judge(map, x, i)) { //满足判断进行下一步递归 init_temp(x, i); dfs(temp, x, i + t, Max + 1); //将遍历过的位置标记，然后继续遍历 } } dfs(map, x + 1, 0, Max);}intmain(){//输入M*N材料的信息cin >> M >> N;for (int i = 0; i < M; i++)for (int j = 0; j < N; j++)cin >> map[i][j];//输入s*t材料的信息cin >> s >> t;for (int i = 0; i < s; i++)for (int j = 0; j < t; j++)cin >> mapb[i][j]; ans = 0; Max = 0; dfs(map, 0, 0, 0);cout << ans << endl; system("pause");return0;}
