hdu 1312

时间:2022-04-29 17:30:05

原题链接

题意:“@”为起点,“.”为路,求可以走的格子有多少个(包括起点)

水题 bfs搜一发

思路:只有可以走的节点才能进入队列,所以每次出队列时ans+1就可以了(没有退出条件,所有可进入的节点都要搜索)

#include "map"
#include "queue"
#include "math.h"
#include "stdio.h"
#include "string.h"
#include "iostream"
#include "algorithm"
#define abs(x) x > 0 ? x : -x
#define max(a,b) a > b ? a : b
#define min(a,b) a < b ? a : b using namespace std; int d[][] = {{,},{,},{,-},{-,}};
bool Map[][],vis[][],f[][];
int n,m,ans; struct Node
{
int xx,yy;
}; void Bfs(int x,int y)
{
memset(vis,,sizeof(vis));
memset(f,,sizeof(f)); Node now,next;
queue<Node>Q; now.xx = x;
now.yy = y;
vis[x][y] = ;
f[x][y] = ;
ans = ; Q.push(now); while(!Q.empty())
{
now = Q.front();
Q.pop(); if(Map[now.xx][now.yy])
ans++; for(int i=; i<; i++)
{
next.xx = now.xx + d[i][];
next.yy = now.yy + d[i][]; if(Map[next.xx][next.yy] && !vis[next.xx][next.yy])
{
vis[next.xx][next.yy] = ;
Q.push(next);
}
}
}
printf("%d\n",ans);
} int main()
{
int i,j,x,y;
char c;
while(scanf("%d%d",&n,&m)&&(n||m))
{
memset(Map,,sizeof(Map));
for(i=; i<=m; i++)
{
getchar();
for(j=; j<=n; j++)
{
scanf("%c",&c);
if(c=='#')
Map[i][j] = ;
if(c=='.')
Map[i][j] = ;
if(c=='@')
{
x=i,y=j;
Map[i][j] = ;
}
}
} Bfs(x,y);
}
return ;
}