poj1979 简单bfs

秒速五厘米 2022-08-21 11:58 171阅读 0赞

题意：

就是给一个矩形，由.和\#还有@组成，\#不能走，然后一个人站在@处，问这个人最多可以走的位置有哪些。

一个简单的bfs，然后看vis数组里面有多少个位置被标记就可以了。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <queue>
    
    using namespace std;
    
    int const maxn = 25;
    char str[maxn][maxn];
    int vis[maxn][maxn];
    int w,h;
    int ex,ey;
    
    int dir[4][2] = {0,1,0,-1,-1,0,1,0};
    
    struct  node
    {
    	int x,y;
    	int step ; 
    };
    
    void bfs()
    {
    	queue<node> q;
    	node cur , next;
    	cur.x = ex , cur.y = ey;
    	cur.step = 0;
    	vis[ex][ey]=1;
    	q.push(cur);
    	while(!q.empty())
    	{
    		cur = q.front();
    		q.pop();
    		for(int i = 0 ; i < 4 ; i++)
    		{
    			next.x = cur.x + dir[i][0];
    			next.y = cur.y + dir[i][1];
    			next.step = cur.step + 1;
    			//cout<<next.x<<" "<<next.y<<" "<<next.step<<endl;
    			if(next.x>=0&&next.x<h&&next.y>=0&&next.y<w
    				&&!vis[next.x][next.y]&&str[next.x][next.y]!='#')
    			{
    				//cout<<next.step<<endl;
    				q.push(next);
    				vis[next.x][next.y] = 1;
    			}
    		}
    	}
    }
    
    int main()
    {
    	while(scanf("%d%d",&w,&h)&&(w||h))
    	{
    		for (int i = 0 ; i < h ; i++)
    		{
    			scanf("%s",str[i]);
    			for(int j = 0 ; j < w ; j++)
    			{
    				if(str[i][j]=='@')
    				{
    					ex = i; 
    					ey = j;
    				}
    			}
    		}
    		memset(vis,0,sizeof(vis));
    		int ans = 0;
    		bfs() ;
    		for(int i = 0 ; i < h ; i++)
    		{
    			for(int j = 0 ; j < w ; j++)
    			{
    				if(vis[i][j])ans++;
    			}
    		}
    		printf("%d\n",ans);
    	}
    	return 0;
    }