算法1
(并查集)
对于每个黑色元素,将上方与左方相连的黑色元素联合,最后再检查一轮,统计与初始位置处于同一个集合的黑色块的数量。
时间复杂度
并查集时间复杂不会算。。。会的教我一下。。。
C++ 代码
#include <iostream>
using namespace std;
int find(int index, int parent[]){
if(index == parent[index]) return index;
return find(parent[index], parent);
}
void uni(int index1, int index2, int parent[]){
parent[find(index2, parent)] = find(index1, parent);
}
void solution(int m, int n){
int x0, y0;
int parent[m * n];
fill(parent, parent + m * n, -1);
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
char c;
cin >> c;
int index = i * n + j;
if(c == '.' || c == '@'){
parent[index] = index;
if(i > 0 && parent[index - n] != -1) uni(index, index-n, parent);
if(j > 0 && parent[index - 1] != -1) uni(index, index-1, parent);
if(c == '@'){
x0 = i;
y0 = j;
}
}
}
}
int root = find(parent[x0 * n + y0], parent), ans = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
int index = i * n + j;
if(parent[index] != -1 && find(index,parent) == root) ans++;
}
}
cout << ans << endl;
}
int main(){
int m = 1, n = 1;
while(m && n){
cin >> n >> m;
if(m && n) solution(m, n);
}
}
算法2
(DFS) $O(n^m)$
以原点为起点深度优先遍历全图
时间复杂度
O(m*n)
参考文献
C++ 代码
#include <iostream>
using namespace std;
int dir[4][2] = {{0,1}, {1,0}, {0,-1},{-1,0}};
int ans;
int vis[21][21], A[21][21];
int m, n;
void DFS(int x, int y){
if(vis[x][y] || !A[x][y]) return;
vis[x][y] = 1;
ans++;
for(int i = 0; i < 4; i++){
if(x + dir[i][0] < 0 || x + dir[i][0] >= m) continue;
if(y + dir[i][1] < 0 || y + dir[i][1] >= n) continue;
DFS(x + dir[i][0], y + dir[i][1]);
}
}
void solution(){
int x, y;
ans = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
char c;
cin >> c;
vis[i][j] = 0;
A[i][j] = c == '#' ? 0 : 1;
if(c == '@'){
x = i;
y = j;
}
}
}
DFS(x, y);
cout << ans << endl;
}
int main(){
m = 1, n = 1;
while(m && n){
cin >> n >> m;
if(m && n) solution();
}
}