poj1979 简单bfs

秒速五厘米 2022-08-21 11:58 148阅读 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;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，148人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 2251 Dungeon Master(简单BFS)

三维立体型迷宫，输入是一层一层向上。 include<cstdio> include<cstring> include<queue> usi

缺乏、安全感/ 2024年02月17日 19:06/ 0 赞/ 50 阅读

相关 POJ-1979（搜索水题）

题目链接-[POJ1979][] Red and Black <table> <tbody> <tr> <td><strong>Time

ゞ浴缸里的玫瑰/ 2022年09月26日 02:17/ 0 赞/ 142 阅读

相关【poj1979】Red and Black

![这里写图片描述][20160729090815398] ![这里写图片描述][20160729090823726] ![这里写图片描述][2016072909083

傷城~/ 2022年09月24日 10:23/ 0 赞/ 121 阅读

相关 poj1979 简单bfs

题意：就是给一个矩形，由.和\还有@组成，\不能走，然后一个人站在@处，问这个人最多可以走的位置有哪些。一个简单的bfs，然后看vis数组里面有多少个位置被标

秒速五厘米/ 2022年08月21日 11:58/ 0 赞/ 149 阅读

相关 poj 1915 Knight Moves【BFS】【简单】

Knight Moves <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS<

待我称王封你为后i/ 2022年08月10日 09:29/ 0 赞/ 49 阅读

相关 poj 3984 迷宫问题【BFS && DFS】【简单】

迷宫问题 <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

布满荆棘的人生/ 2022年08月10日 09:16/ 0 赞/ 190 阅读

相关 (简单双向BFS)poj1915 Knight Moves

题目链接：[poj1915 Knight Moves][] 比起单向要省时得多。 include <iostream> include <cstdio>

àì夳堔傛蜴生んèń/ 2022年03月18日 08:50/ 0 赞/ 145 阅读

相关 poj 3126 BFS

BFS得到的一定是最短路径。开始我还在纠结怎么才是最短的呢。其实BFS的题目有个共性（这不废话，哪一类题没有共性啊。呵呵）。以后做这种题自己慢慢总结吧。

柔情只为你懂/ 2021年12月17日 02:57/ 0 赞/ 361 阅读

相关 poj3414_bfs

题意：这个题以前见过，但是从没有用代码实现过，题意就是，给出两个杯子的容量，求是否可以通过fill,drop,pour,一系列操作，最后得出某一个容量的液体，如果可以则输出最少

淩亂°似流年/ 2021年12月08日 19:55/ 0 赞/ 294 阅读

相关 DFS解决POJ 1979

Description There is a rectangular room, covered with square tiles. Each tile is

淡淡的烟草味﹌/ 2021年11月11日 11:50/ 0 赞/ 224 阅读