404

題目描述

有一個(gè)N x M 大小的地圖，地圖中的每個(gè)單元包含一個(gè)大寫字母。
若兩個(gè)相鄰的(這里的相鄰指“上下左右”相鄰)點(diǎn)上的字母相同，我們可以用線段連接這兩個(gè)點(diǎn)。
若存在一個(gè)包含同一字母的環(huán)路，那么連接這些點(diǎn)我們可以得到一個(gè)多邊形，
當(dāng)且僅當(dāng)多邊形的邊數(shù)大于等于4時(shí)，我們稱這幅地圖中存在“簡單環(huán)路”。
現(xiàn)在給你一份地圖，你來判斷是否存在“簡單環(huán)路”。
列如：
3 4
AAAA
ABCA
AAAA
字符“A”可以構(gòu)成一個(gè)“簡單環(huán)路”，其邊數(shù)為4。

輸入

第一行輸入兩個(gè)正整數(shù)n,m，2<=n,m<=50，分別表示地圖的行列數(shù)。
接下來輸入n行，每行m個(gè)大寫字母。

輸出

若存在“簡單環(huán)路”輸出“Yes”，否則輸出“No”。

樣例輸入

3 4
AAAA
ABCA
AADA

樣例輸出

No

思路

并查集，把每個(gè)相同的點(diǎn)合成一個(gè)祖先。如果遇到兩個(gè)點(diǎn)相同，而且他們的祖先也相同，那么就形成環(huán)了。

AC

#include<bits/stdc++.h> #define ll long long #define mem(a, b) memset(a, b, sizeof(a)) #define N 105 using namespace std; char g[N][N]; int n, m; int pre[N * N]; // 獲取每個(gè)坐標(biāo)的唯一id int id(int i, int j) {return i * m + j; } //祖先初始化 void init() {for (int i = 0; i < N * N; i++) {pre[i] = i;} } // 查找祖先 int find (int x) {if (x == pre[x]) return x;else return pre[x] = find(pre[x]); } int main() { // freopen("in.txt", "r", stdin);while (scanf("%d%d", &n, &m) != EOF) {for (int i = 0; i < n; i++) {scanf("%s", &g[i]);}init();int flag = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {//左右方向 if (g[i][j] == g[i][j + 1]) {int u = id(i, j);int v = id(i, j + 1);int find_u = find(u);int find_v = find(v);if (find_u != find_v) {pre[find_u] = pre[find_v];find(find_u);}else {flag = 1;break;}}//上下方向 if (g[i][j] == g[i + 1][j]) {int u = id(i, j);int v = id(i + 1, j);int find_u = find(u);int find_v = find(v); if (find_u != find_v) {pre[find_u] = pre[find_v];find(find_u);}else {flag = 1;break;}}}if (flag) break;}if (flag) printf("Yes\n");else printf("No\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2025 : 简单环路（并查集）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。