用的1101题目类似,搜索
用的队列实现bfs,搜到一个合适的位置就让cnt++。
因为有多组输入 注意每次运算之前需要初始化各个数组
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=25;
int w,h;
int a[N][N];
char c;
bool st[N][N];//标记位置有没有走过
int bfs(PII start){
memset(st,false,sizeof st);
int cnt=1;//起点已经包含
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
PII t;
queue<PII> Q;
Q.push(start);
st[start.x][start.y]=true;
while(Q.size()){
t=Q.front();Q.pop();
for(int i=0;i<4;i++){//枚举四个方向
int x=t.x+dx[i],y=t.y+dy[i];
if(x<1||x>h||y<1||y>w)continue;//越界
if(st[x][y])continue;//已经遍历过
if(a[x][y]==0){st[x][y]=true;continue;}
if(a[x][y]==1){
cnt++;
// cout<<"!"<<x<<y<<"\n";
Q.push({x,y});
st[x][y]=true;
}
}
// cout<<"!"<<Q.size()<<"\n";
}
return cnt;
}
int main()
{
while(cin>>w>>h&&w!=0){
PII start;
memset(a,0,sizeof a);
for(int i=1;i<=h;i++)
for(int j=1;j<=w;j++){
cin>>c;
if(c=='#')a[i][j]=0;//红
else if(c=='.') a[i][j]=1;//黑,可以走
else{//起点
a[i][j]=1;
start={i,j};
}
}
//cout<<start.x<<start.y<<"\n";
int res=bfs(start);
cout<<res<<"\n";
}
return 0;
}