红与黑

题目描述

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

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

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

算法1 dfs

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=22;
char g[N][N];
int vis[N][N];
int w,h,ans=1;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
void dfs(int beginx,int beginy){
    for(int i=0;i<4;i++){
        int x=beginx+dx[i],y=beginy+dy[i];
        if(x<0||y<0||x>=h||y>=w) continue;
        if(g[x][y]=='#'||vis[x][y]) continue;
        if(!vis[x][y]&&g[x][y]=='.'){
            vis[x][y]=1;
            ans++;
            dfs(x,y);
        }
    }
}
int main(){
    while(1){
        ans=1;
        cin>>w>>h;
        if(w==0&&h==0) break;
        for(int i=0;i<h;i++) scanf("%s",g[i]);
        int beginx,beginy;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(g[i][j]=='@'){
                    beginx=i;
                    beginy=j;
                }
            }
        }
        dfs(beginx,beginy);
        cout<<ans<<endl;
        memset(vis,0,sizeof vis);
    }
    return 0;
}

算法2 bfs

C++ 代码

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=25;
char g[N][N];
int vis[N][N];
int w,h;
int dx[4]={0,-1,0,1};
int dy[4]={1,0,-1,0};
int bfs(PII start){
    int res=1;
    queue<PII> q;
    q.push(start);
    memset(vis,0,sizeof vis);
    while(q.size()){
        PII t=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int x=t.x+dx[i];
            int y=t.y+dy[i];
            if(x<0||y<0||x>=h||y>=w) continue;
            if(vis[x][y]) continue;
            vis[x][y]=1;
            if(g[x][y]=='#') continue;
            if(g[x][y]=='.') res++;
            q.push({x,y});
        }
    }
    return res;
}
int main(){
    while(1){
        cin>>w>>h;
        if(w==0&&h==0) break;
        for(int i=0;i<h;i++) scanf("%s",g[i]);
        PII start;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(g[i][j]=='@') start={i,j};
            }
        }
        int res=bfs(start);
        cout<<res<<endl;
    }
    return 0;
}