连通性

Acwing 1112. 迷宫

一天 $E x t e n s e$ 在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 n∗n 的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。

同时当 $E x t e n s e$ 处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上， $E x t e n s e$ 想要从点A走到点B，问在不走出迷宫的情况下能不能办到。

如果起点或者终点有一个不能通行(为#)，则看成无法办到。

注意：A、B不一定是两个不同的点。

输入格式

第1行是测试数据的组数 $k$ ，后面跟着 $k$ 组输入。

每组测试数据的第1行是一个正整数 $n$ ，表示迷宫的规模是 $n * n$ 的。

接下来是一个 $n * n$ 的矩阵，矩阵中的元素为.或者#。

再接下来一行是 4 个整数 $h a, l a, h b, l b$ ，描述 $A$ 处在第 $h a$ 行, 第 $l a$ 列，B 处在第 $h b$ 行, 第 $l b$ 列。

注意到 $h a, l a, h b, l b$ 全部是从 0 开始计数的。

输出格式

k行，每行输出对应一个输入。

能办到则输出“YES”，否则输出“NO”。

数据范围

$1 \leq n \leq 100$

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#include<unordered_map>
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
    return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<int, string>PIS;
typedef pair<int, PII>PIII;
const int N = 110;
int n;
char g[N][N];
bool vis[N][N];
int xa, ya, xb, yb;
int dx[4] = {
    0,-1,0,1 }, dy[4] = {
    1,0,-1,0 };

bool dfs(int x, int y) {
   
	if (g[x][y] == '#')return false;
	if (x == xb && y == yb)return true;
	vis[x][y] = true;


	for (int i = 0; i < 4; ++i) {
   
		int a = x + dx[i];
		int b = y + dy[i];

		if (a < 0 || a >= n || b < 0 || b >= n)continue;
		if (vis[a][b])continue;

		if (dfs(a, b))return true;

	}
	return false;
}
int main() {
   
	int t; cin >> t;
	while (t--) {
   
		memset(vis, 0, sizeof vis);
		cin >> n;
		for (int i = 0; i < n; ++i)scanf("%s", g[i]);
		cin >> xa >> ya >> xb >> yb;
		if (dfs(xa, ya))puts("YES");
		else puts("NO");
	}

	return 0;
}

AcWing1113. 红与黑

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。

你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。

请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入格式

输入包括多个数据集合。

每个数据集合的第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。

在接下来的 H 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下

1）‘.’：黑色的瓷砖；
2）‘#’：白色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

当在一行中读入的是两个零时，表示输入结束。

输出格式

对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

数据范围

$1 \leq W, H \leq 20$

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#include<unordered_map>
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
    return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<int, string>PIS;
typedef pair<int, PII>PIII;
const int N = 110;
int n, m;
char g[N][N];
bool vis[N][N];
int sx, sy;
int dx[4] = {
    0,-1,0,1 }, dy[4] = {
    -1,0,1,0 };
int dfs(int x, int y) {
   
	int cnt = 1;
	vis[x][y] = true;

	for (int i = 0; i < 4; ++i) {
   
		int a = x + dx[i];
		int b = y + dy[i];

		if (a < 0 || a >= n || b < 0 || b >= m)continue;
		if (g[a][b] != '.' || vis[a][b])continue;

		cnt += dfs(a, b);
	}
	return cnt;
}

int main() {
   
	while (cin >> m >> n, n || m) {
   
		for (int i = 0; i < n; ++i)scanf("%s", g[i]);

		for (int i = 0; i < n; ++i) {
   
			for (int j = 0; j < m; ++j) {
   
				if (g[i][j] == '@') {
   
					sx = i;
					sy = j;
				}
			}
		}
		memset(vis, 0, sizeof vis);
		cout << dfs(sx, sy) << endl;
	}

	return 0;
}

搜索顺序

AcWing1116. 马走日

马在中国象棋以日字形规则移动。

请编写一段程序，给定 n∗m 大小的棋盘，以及马的初始位置 (x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。

输入格式

第一行为整数 T，表示测试数据组数。

每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标 n,m,x,y.

输出格式

每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，若无法遍历棋盘上的所有点则输出 0。

数据范围

$1 \leq T \leq 9$
$1 \leq m, n \leq 9$
$0 \leq x \leq n - 1$
$0 \leq y \leq m - 1$

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#include<unordered_map>
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
    return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<int, string>PIS;
typedef pair<int, PII>PIII;
const int N = 15;
bool vis[N][N];
int n, m;
int ans;
int dx[8] = {
    -2,-2,-1,1,2,2,1,-1 }, dy[8] = {
    -1,1,2,2,1,-1,-2,-2 };
void dfs(int x, int y, int cnt) {
   
	if (cnt == n * m ) {
   
		ans++;
		return;
	}
	vis[x][y] = true;
	for (int i = 0; i < 8; ++i) {
   
		int a = x + dx[i];
		int b = y + dy[i];
		if (a < 0 || a >= n || b < 0 || b >= m)continue;
		if (vis[a][b])continue;
		dfs(a, b, cnt + 1);
	}
	vis[x][y] = false;
}
int main() {
   
	int t; cin >> t;
	while (t--) {
   
		ans = 0;
		memset(vis, 0, sizeof vis);
		cin >> n >> m;
		int x, y;
		cin >> x >> y;
		dfs(x, y, 1);
		cout << ans << endl;
	}
}

AcWing1117. 单词接龙

单词接龙是一个与我们经常玩的成语接龙相类似的游戏。

现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”，每个单词最多被使用两次。

在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish ，如果接成一条龙则变为 beastonish。

我们可以任意选择重合部分的长度，但其长度必须大于等于1，且严格小于两个串的长度，例如 at 和 atide 间不能相连。

输入格式

输入的第一行为一个单独的整数 n 表示单词数，以下 n 行每行有一个单词（只含有大写或小写字母，长度不超过20），输入的最后一行为一个单个字符，表示“龙”开头的字母。

你可以假定以此字母开头的“龙”一定存在。

输出格式

只需输出以此字母开头的最长的“龙”的长度。

数据范围

$n \leq 20$

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#include<unordered_map>
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
    return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<int, string>PIS;
typedef pair<int, PII>PIII;
const int N = 50;
string word[N];
int n;
int g[N][N];
int used[N];
int ans;
void dfs(string dragon, int last) {
   
	ans = max((int)dragon.size(), ans);

	used[last]++;
	for (int i = 0; i < n; ++i) {
   
		if (g[last][i] && used[i] < 2) {
   
			dfs(dragon + word[i].substr(g[last][i]), i);
		}
	}
	used[last]--;
}
int main() {
   
	cin >> n;
	for (int i = 0; i < n; ++i)cin >> word[i];
	char start; cin >> start;
	for (int i = 0; i < n; ++i) {
   
		for (int j = 0; j < n; ++j) {
   
			string a = word[i], b = word[j];
			for (int k = 1; k <= min(a.size(), b.size());++k) {
   
				if (a.substr(a.size() - k, k) == b.substr(0, k)) {
   
					g[i][j] = k;
					break;
				}
			}
		}
	}

	for(int i = 0;i <n;++i){
   
		if (word[i][0] == start)
			dfs(word[i], i);
	}

	cout << ans << endl;
}

AcWing 1118. 分成互质组

给定 n 个正整数，将它们分组，使得每组中任意两个数互质。

至少要分成多少个组？

输入格式

第一行是一个正整数 n。

第二行是 n 个不大于10000的正整数。

输出格式

一个正整数，即最少需要的组数。

数据范围

1≤n≤10

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#include<unordered_map>
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
    return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<int, string>PIS;
typedef pair<int, PII>PIII;
const int N = 50;
int n;
int a[N], g[N][N];
bool vis[N];
int ans = INF;

bool check(int g[], int sum,int x) {
   
	for (int i = 0; i < sum; ++i) {
   
		if (gcd(g[i], x) > 1)return false;
	}
	return true;
}

void dfs(int u, int gc, int tc, int start) {
    //从第u组 组内有gc个元素 一共选了tc个数 从start开始搜
	if (u >= ans)return;
	if (tc == n)ans = min(ans, u);
	bool flag = true;
	for (int i = start; i <= n; ++i) {
   
		if (!vis[i] && check(g[u], gc,a[i])) {
   
			vis[i] = true;
			g[u][gc] = a[i];
			dfs(u, gc + 1, tc + 1, i + 1);
			vis[i] = false;
			flag = false;
		}
	}
	if (flag)dfs(u + 1, 0, tc, 1);
}

int main() {
   
	cin >> n;
	for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);

	dfs(1, 0, 0, 1);
	cout << ans << endl;
}

DFS之连通性和搜索顺序

连通性

Acwing 1112. 迷宫

输入格式

输出格式

数据范围

代码

AcWing1113. 红与黑

输入格式

输出格式

数据范围

代码

搜索顺序

AcWing1116. 马走日

输入格式

输出格式

数据范围

代码

AcWing1117. 单词接龙

输入格式

输出格式

数据范围

代码

AcWing 1118. 分成互质组

输入格式

输出格式

数据范围

代码