题目

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。

你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。

请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

样例

输入

6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0

输出：

45

算法

bfs dfs
代码参考来源 yxc

C++ 代码一

//bfs 是出一个 res加一一次
///而dfs是递归一次 就有一次加res
//且每一次调用的初值res为1 即等同于每次加一
//把去过的地方变为墙 就可以不用额外开visit【】了

#include<iostream>
#include<queue>
#include<algorithm>
#define x first
#define y second 
using namespace std;
typedef pair< int, int> PII;//队列需要队列类型和变量类型  这里定义变量类型为一对数字 
const int N = 25;
int n,m;
char g[N][N];
int bfs(int sx, int sy){
    queue<PII> q;   
    q.push({sx, sy});
    g[sx][sy] = '#';
    int res = 0;    
    int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
    while(q.size())
    {
        auto t = q.front(); 
        q.pop();        
        res++;  

        for(int i = 0; i < 4; i++ ){
            int x = t.x + dx[i], y = t.y +dy[i];
            if(x < 0|| x >=n || y >= m || g[x][y] != '.') continue;
            g[x][y] = '#';
            q.push({x,y});
        }  //从搜过的没越界也不是障碍物的地方  往四周搜索 
    }
    return res;
}
int main(){ 
    while(cin>>m>>n, m||n){
        for(int i = 0; i < n; i++ ) cin>>g[i];
        int x,y;
        for(int i = 0; i < n; i++ ){            
            for(int j = 0; j < m; j++){
                if(g[i][j]=='@'){ 
                    x = i; y =j;
                }
            }
        }
    cout << bfs(x,y) << endl;   
    }
    return 0;
}

struct 替代pair 版本

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int N =25;
int n,m; char g[N][N];
int dx[5]={-1,0,1,0},dy[5]={0,1,0,-1};
struct node{
    int x,y;    
}tmp;
int bfs(int sx,int sy){
    int res = 0;
    queue<node> q;
    q.push({sx,sy});
    while(q.size()){
        tmp = q.front();
        q.pop();
        res++;
        for(int i = 0;i <4;i++){
            int x = tmp.x +dx[i],y = tmp.y +dy[i];
            if(x<0||x>n||y<0||y>m||g[x][y]!='.') continue;
            g[x][y] = '#';
            q.push({x,y});
        }
    }
    return res;
}
int main(){
    int ans = 0;
    while(cin>>m>>n, m||n){
    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]=='@'){
                ans = bfs(i,j);
                break;
            }
        }
    }
    cout<<ans<<endl;
    }
    return 0;
}

C++ 代码二

//dfs版本    即递归！！
#include<iostream>
#include<algorithm> 
using namespace std;
const int N = 25;
int n,m;
char g[N][N];
int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
int dfs(int x, int y)
{
    int res = 1;
    g[x][y] = '#';
    for(int i = 0; i < 4; i++ ){
        int a = x + dx[i], b = y + dy[i];
        if(a >= 0 && a < n && b >= 0 && b < m && g[a][b] == '.')
            res += dfs(a,b); 
    }
    return res;
}
int main(){ 
    while(cin>>m>>n, m||n){
        for(int i = 0; i < n; i++ ) cin>>g[i];
        int x,y;
        for(int i = 0; i < n; i++ ){            
            for(int j = 0; j < m; j++){
                if(g[i][j]=='@'){ 
                    x = i; y =j;
                }
            }
        }
    cout << dfs(x,y) << endl;   
    }
    return 0;
}