1、 单词接龙
https://www.luogu.org/problemnew/show/P1019
题目描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beastbeast和astonishastonish，如果接成一条龙则变为beastonishbeastonish，另外相邻的两部分不能存在包含关系，例如atat 和 atideatide 间不能相连。
输入输出格式
输入格式：
输入的第一行为一个单独的整数nn (n \le 20n≤20)表示单词数，以下nn 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出格式：
只需输出以此字母开头的最长的“龙”的长度。
输入输出样例
输入样例#1：
5 at touch cheat choose tact a
输出样例#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;
}
;
}