蒟蒻只会暴搜了
要点是先找到起点,从起点开始向各个方向搜
DFS:
(DFS当然也可以用for(int i=0;i,4;i++)来搜索四个方向,这里是个人习惯)
#include<iostream>
#include<cstring>
using namespace std;
const int N=30;
char map[N][N];
int n,m,cnt=1;
int flagx,flagy;
void dfs(int x,int y)
{
if(x<0 || x>=n || y<0 || y>=m || map[x][y]=='#') return;
if(map[x][y]=='.')cnt++;
map[x][y]='#';
dfs(x+1,y),dfs(x-1,y),dfs(x,y+1),dfs(x,y-1);
}
void find()
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
if(map[i][j]=='@')
{
flagx=i,flagy=j;
return;
}
}
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF && m!=0 || n!=0)
{
cnt=0;
for(int i=0;i<n;i++) scanf("%s",map[i]);
find();
dfs(flagx,flagy);
cout<< cnt <<endl;
}
return 0;
}
BFS:
#include<iostream>
#include<cstring>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 30;
char g[N][N];
int n, m;
int flagx, flagy;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
bool st[N][N];
int bfs(int x, int y)
{
int cnt=1;
queue<PII>q;
q.push({x,y});
while(q.size())
{
PII t = q.front();
q.pop();
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)continue;//出界
if(st[a][b])continue;//遍历过
if(g[a][b] == '#')continue;//不可走
q.push({a,b});
st[a][b]=true;
cnt++;
}
}
return cnt;
}
void find()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
if (g[i][j] == '@')
{
flagx = i, flagy = j;
return;
}
}
}
int main()
{
while (cin >> m >> n && n || m)
{
memset(st, 0, sizeof st);
for (int i = 0; i < n; i++) scanf("%s", g[i]);
find();
cout << bfs(flagx, flagy) << endl;
}
return 0;
}
标签:cnt,int,红与黑,dfs,st,++,1113,include,AcWing From: https://www.cnblogs.com/lxl-233/p/16839454.html