用并查集将字母相同的邻居合并,如果在合并前两个节点的根节点相同说明存在环
const int N = 510;
int dx[] = {0,1};
int dy[] = {1,0};
class Solution {
public:
int n, m;
int p[N*N];
int getX(int i, int j){
return i *m + j;
}
int find(int x){
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
bool containsCycle(vector<vector<char>>& grid) {
n = grid.size(), m = grid[0].size();
memset(p, -1, sizeof p);
for (int i = 0; i<n; i++)
for (int j = 0; j<m; j++)
p[getX(i, j)] = getX(i, j);
for (int i = 0; i<n; i++)
for (int j = 0; j <m; j++){
for (int k = 0; k < 2; k++){
int x_ne = i + dx[k], y_ne = j + dy[k];
if (x_ne >= n || y_ne >= m) continue;
if (grid[i][j] != grid[x_ne][y_ne]) continue;
int pa = find(getX(i, j)), pb = find(getX(x_ne, y_ne));
if (pa == pb) return true;
p[pa] = pb;
}
}
return false;
}
};