算法模板（3）：搜索（6）：做题积累 一、DFS 1. 1113. 红与黑
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖 。你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动 。请写一个程序，计算你总共能够到达多少块黑色的瓷砖 。
#include#include#includeusing namespace std;const int maxn = 25;char mz[maxn][maxn];int N, M, sx, sy, tx, ty, dx[] = { 1, -1, 0, 0 }, dy[] = {0, 0, 1, -1};bool vis[maxn][maxn];int dfs(int x, int y) {int cnt = 1;vis[x][y] = true;for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;if (vis[nx][ny] || mz[nx][ny] != '.') continue;cnt += dfs(nx, ny);}return cnt;}int main() {while (cin >> M >> N && N) {memset(vis, false, sizeof vis);for (int i = 0; i < N; i++) {cin >> mz[i];}int sx, sy;for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (mz[i][j] == '@') {sx = i, sy = j;break;}}}cout << dfs(sx, sy) << endl;}return 0;}
2.of the Bone
#include#include#include#includeusing namespace std;char g[10][10];bool vis[10][10];int N, M, t, sx, sy, gx, gy;int dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 };bool dfs(int x, int y, int total) {if (total > t) return false;if (total == t && g[x][y] == 'D') return true;//奇偶性剪枝（可行性剪枝）if (abs(t - total - abs(x - gx) - abs(y - gy)) & 1) return false;vis[x][y] = true;for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;if (g[nx][ny] == 'X' || vis[nx][ny]) continue;if (dfs(nx, ny, total + 1)) return true;}vis[x][y] = false;return false;}int main() {while (cin >> N >> M >> t, N) {memset(vis, false, sizeof vis);int block = 0;for (int i = 0; i < N; i++) cin >> g[i];for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (g[i][j] == 'S') sx = i, sy = j;else if (g[i][j] == 'D') gx = i, gy = j;else if (g[i][j] == 'X') block++;}}if (N * M - block < t || abs(abs(sx - gx) + abs(sy - gy) - t) & 1) printf("NO\n");else if (dfs(sx, sy, 0)) printf("YES\n");else printf("NO\n");}return 0;}
3. 1116. 马走日
#include#include#includeusing namespace std;int N, M, sx, sy, ans;int dy[] = { -2, -1, 1, 2, 2, 1, -1, -2 }, dx[] = { -1, -2, -2, -1, 1, 2, 2, 1 };bool vis[15][15];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 nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;if (vis[nx][ny]) continue;dfs(nx, ny, cnt + 1);}vis[x][y] = false;}int main() {int T;scanf("%d", &T);while (T--) {scanf("%d%d%d%d", &N, &M, &sx, &sy);ans = 0;dfs(sx, sy, 1);printf("%d\n", ans);}return 0;}
4. 1117. 单词接龙
#includeusing namespace std;const int maxn = 25;int g[maxn][maxn], N, ans = 0, used[maxn];string words[maxn], head;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 + words[i].substr(g[last][i]), i);}}used[last]--;}int main() {cin >> N;for (int i = 0; i < N; i++) {cin >> words[i];}cin >> head;for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {string& s1 = words[i], & s2 = words[j];for (int k = 1; k < min(s1.size(), s2.size()); k++) {if (s1.substr(s1.size() - k, k) == s2.substr(0, k)) {g[i][j] = k;break;}}}}for (int i = 0; i < N; i++) {if (words[i][0] == head[0]){dfs(head + words[i].substr(1), 0);}}cout << ans << endl;return 0;}
5. 1118. 分成互质组
#includeusing namespace std;const int maxn = 15;//group存放的是数字的下标int group[maxn][maxn], p[maxn], N, ans = 10;bool vis[maxn];int gcd(int a, int b) {if (b == 0) return a;return gcd(b, a % b);}bool check(int g[], int gc, int idx) {for (int i = 0; i