题目 45 这道题bfs暴力搜索
#include <bits/stdc++.h> using namespace std; const int N=25; int w,h,sx,sy,sum; char mat[N][N]; int vis[N][N]={0}; int dx[4]={1,-1,0,0}; int dy[4]={0,0,-1,1}; struct node{ int x,y; }; void bfs(int x,int y){ queue<node>que; que.push(node{sx,sy}); vis[sx][sy]=1; while(que.size()){ node now=que.front(); que.pop(); for(int i=0;i<4;i++){ int xx=now.x+dx[i]; int yy=now.y+dy[i]; if(!vis[xx][yy]&&xx>0&&xx<=h&&yy>0&&yy<=w&&mat[xx][yy]=='.'){ vis[xx][yy]=1; mat[xx][yy]='*'; sum++; //cout<<xx<<' '<<yy<<endl; que.push(node{xx,yy}); } } } } int main(){ cin>>w>>h; sum=1; for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++){ cin>>mat[i][j]; if(mat[i][j]=='@'){ sx=i; sy=j; } } } bfs(sx,sy); cout<<sum<<endl; return 0; }另一种dfs的方法
#include<cstdio> #include<iostream> #include<queue> using namespace std; char map[40][40]; int dir[4][2]= {{1,0},{0,1},{0,-1},{-1,0}}; //走的方向 int sum=1; int row,col; struct node { int x,y; } start; //start为起点 queue<node> a; void bfs() { node tmp1,tmp2; a.push(start); while(!a.empty()) { tmp1=a.front(); a.pop(); for(int i=0; i<4; i++) //4个方向搜索 满足条件的插入队尾 { tmp2.x=tmp1.x+dir[i][0]; tmp2.y=tmp1.y+dir[i][1]; if(tmp2.x>=0&&tmp2.x<row&&tmp2.y>=0&&tmp2.y<col&&map[tmp2.x][tmp2.y]=='.') { sum++; map[tmp2.x][tmp2.y]='#'; //对搜索到的黑瓷砖进行标记 a.push(tmp2); } } } } int main() { cin>>col>>row; for(int i=0; i<row; i++) { for(int j=0; j<col; j++) { cin>>map[i][j]; if (map[i][j]=='@') { start.x=i; start.y=j; } } } bfs(); cout<<sum<<endl; }