dfs
#include <iostream>
#include <cstring>
using namespace std;
int n, m, x, y;
int ans;
char a[22][22];
int vis[22][22];
int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};
void dfs(int x, int y){
vis[x][y] = 1;
for(int i = 0; i < 4; i ++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 1 || nx > n || ny < 1 || ny > m || a[nx][ny] == '#' || vis[nx][ny]) continue;
ans ++;
dfs(nx, ny);
}
}
int main(){
while(1){
cin >> m >> n;
if(n == 0 && m == 0) return 0;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
cin >> a[i][j];
if(a[i][j] == '@'){
x = i;
y = j;
}
}
}
dfs(x, y);
cout << ans + 1 << endl;
memset(vis, 0, sizeof vis);
ans = 0;
}
}
bfs
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int n, m;
int ans;
char a[22][22];
int vis[22][22];
int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};
struct node{
int x, y;
char ch;
}first;
void bfs(node f){
queue <node> q;
q.push(f);
while(!q.empty()){
node now = q.front();
q.pop();
for(int i = 0; i < 4; i ++){
node next;
next.x = now.x + dx[i];
next.y = now.y + dy[i];
next.ch = a[next.x][next.y];
if(next.x < 1 || next.x > n || next.y < 1 || next.y > m || next.ch == '#' || vis[next.x][next.y]) continue;
vis[next.x][next.y] = 1;
q.push(next);
ans ++;
}
}
cout << ans + 1 << endl;
}
int main(){
while(1){
cin >> m >> n;
if(n == 0 && m == 0) return 0;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
cin >> a[i][j];
if(a[i][j] == '@'){
first.x = i;
first.y = j;
vis[i][j] = 1;
}
}
}
bfs(first);
memset(vis, 0, sizeof vis);
ans = 0;
}
}
并查集
#include <iostream>
#include <cstring>
using namespace std;
int n, m, x, y;
int ans;
char a[22][22];
pair<int,int> fa[22][22];
int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};
pair<int,int> find(int x, int y){
return make_pair(x, y) == fa[x][y] ? make_pair(x, y) : fa[x][y] = find(fa[x][y].first, fa[x][y].second);
}
void merge(int x1, int y1, int x2, int y2){
if(find(x1, y1) != find(x2, y2) && a[x1][y1] == a[x2][y2]){
fa[find(x1, y1).first][find(x1, y1).second] = find(x2, y2);
}
}
int main(){
while(1){
cin >> m >> n;
if(n == 0 && m == 0) return 0;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
fa[i][j] = make_pair(i, j);
cin >> a[i][j];
if(a[i][j] == '@'){
a[i][j] = '.';
x = i;
y = j;
}
}
}
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
for(int k = 0; k < 4; k ++){
int ni = i + dx[k];
int nj = j + dy[k];
if(ni < 1 || ni > n || nj < 1 || nj > m) continue;
merge(i, j, ni, nj);
}
}
}
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
if(find(i, j) == find(x, y))ans ++;
}
}
cout << ans << endl;
ans = 0;
}
}