1、 单词接龙
https://www.luogu.org/problemnew/show/P1019
题目描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beastbeast和astonishastonish，如果接成一条龙则变为beastonishbeastonish，另外相邻的两部分不能存在包含关系，例如atat 和 atideatide 间不能相连。
输入输出格式
输入格式：
输入的第一行为一个单独的整数nn (n \le 20n≤20)表示单词数，以下nn 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出格式：
只需输出以此字母开头的最长的“龙”的长度。
输入输出样例
输入样例#1：
5attouchcheatchoosetacta
输出样例#1：
23
核心函数：
计算两个字符串的尾首公共部分长度，不存在返回0
int splice(string s1, string s2) { , j = ; string help1, help2; && j < s2.length() - ) { help1.insert(, , s1[i]); help2.append(, s2[j]); ) return help1.length(); i--; j++; } ;}
完整代码：
#include <iostream>#include <string>#include <algorithm>#include <vector>#include <map>using namespace std;;vector<string>v;];int splice(string s1, string s2) { , j = ; string help1, help2; && j < s2.length() - ) { help1.insert(, , s1[i]); help2.append(, s2[j]); ) return help1.length(); i--; j++; } ;}void DFS(string help) { bool flag = true;//标记，当本层递归没有一个字符串可以往后加时，退出 ; i < v.size(); i++) { int cnt = splice(help, v[i]); && cnt != ) { flag = false; use[i]++; string t = help; DFS(help.append(v[i].substr(cnt))); help = t; use[i]--; } } if (flag) { if (help.length() > maxcnt)maxcnt = help.length(); return; }}int main() { int n; string s; cin >> n; while (n--) { cin >> s; v.push_back(s); } char head; cin >> head; ; i < v.size(); i++) { ] == head) { //不确定是否只有一个龙头 use[i]++; DFS(v[i]); use[i]--; } } cout << maxcnt << endl; ;}
2、单词方阵
https://www.luogu.org/problemnew/show/P1101
给一个n×n的字母方阵，内可能蕴含多个“yizhong”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 8 个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间可以交叉,因此有可能共用字母。输出时，将不是单词的字母用*代替，以突出显示单词。例如：
输入： 8 输出： qyizhong *yizhong gydthkjy gy****** nwidghji n*i***** orbzsfgz o**z**** hhgrhwth h***h*** zzzzzozo z****o** iwdfrgng i*****n* yyyygggg y******g每碰到一个’y’，八向搜索。如果满足该方向的条件就递归，否则结束递归。用数组保存递归路径。
#include <iostream>#include <string>#include <algorithm>#include <vector>#include <map>using namespace std;string standard = "yizhong";int n;][];//上，下，左，右，左上，左下，右上，右下//每个方向x,y的增量][] = { {-,},{,},{,-}, {,},{-,-},{,-},{-,},{,} };][];//记录下路径][];void DFS(int x, int y, int k,int dir) { || x == n || y < || y == n)return; if (k == standard.length()) { ; i < ; i++) { res[path[i][]][path[i][]] = standard[i]; } return; } ]][y + direction[dir][]] == standard[k]) { path[k][] = x + direction[dir][]; path[k][] = y + direction[dir][]; DFS(x + direction[dir][], y + direction[dir][], k + , dir); }}int main() { cin >> n; ; i < n; i++) { ; j < n; j++) { cin >> m[i][j]; } } ; x < n; x++) { ; y < n; y++) { if (m[x][y] == 'y') { ; i < ; i++) { path[][] = x; path[][] = y; DFS(x, y, , i); } } } } ; x < n; x++) { ; y < n; y++) { ) cout << res[x][y]; else cout << '*'; } cout << endl; } ;}
3、迷宫
https://www.luogu.org/problemnew/show/P1605
#include <iostream>using namespace std;//上下左右][] = { {-,},{,},{,-},{,} };][];int N, M, T, cnt;int SX, SY, EX, EY;void DFS(int x, int y) { || x>N || y < || y > M) return; if (x == EX && y == EY) { cnt++; return; } ; i < ; i++) { ]][y + direction[i][]] != ) { m[x + direction[i][]][y + direction[i][]] = ; DFS(x + direction[i][], y + direction[i][]); m[x + direction[i][]][y + direction[i][]] = ; } }}int main() { cin >> N >> M >> T; cin >> SX >> SY >> EX >> EY; ; i < T; i++) { int x,y; cin >> x >> y; m[x][y] = ; } m[SX][SY] = ; DFS(SX, SY); cout << cnt << endl; ;}
P1162 填涂颜色
取巧一点的做法，把外面的0变成-1，就和里面的区分出来，但是外面的0一不一定是连通的，可以把所有边界走完一遍，所有是0的都进行DFS函数一次。
但是，有简单的办法，数组多开一圈，这一圈置0，那么边界0就一定是连通的了，一次DFS就行了。
#include <iostream>#include <stdio.h>using namespace std;][];int n;][] = { {-,},{,},{,-},{,} };void DFS(int x, int y, int sign) { || y < || x > n + || y > n + ) return; ; i < ; i++) { ], toy = y + dir[i][]; if (m[tox][toy] == sign) { m[tox][toy] = -; DFS(tox, toy, sign); } }}int main() { cin >> n; ; i <= n; i++) { ; j <= n; j++) { cin >> m[i][j]; } } DFS(, , ); ; i <= n; i++) { ; j <= n; j++) { )cout << << ' '; )cout << << ' '; << ' '; } cout << endl; } ;}
