本文主要是介绍hdu 1241 || poj 1562 Oil Deposits(搜索:BFS水题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
很水的一道题啊,写了一个多小时...
刚开始读数据的时候用getchar4个样例中有的能读入正确,有的不能...感觉很奇葩
然后改用读入字符串
最要说的一个问题是因为中间用全局变量总有一个bug!!!
查了好一会才查出来...以后要注意了!
在杭电上交题老师MLE, 明明就只有100*100的数组
看到下面评论说这个题好像很怪,有的人说同样一份代码隔了一天交居然就过了
而且有的人代码连样例都过不了也AC了...
于是我倒poj上交题,内存才200+,16msAC
实在是奇怪啊...
代码如下:
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 101
#define LL long long
using namespace std;int m, n, g[MAXN][MAXN];
struct Node {int x, y;
};
int dir[8][2] = {{-1,-1}, {-1,0}, {-1,+1}, {0,-1}, {0,+1}, {+1,-1}, {+1,0}, {+1,+1}};
queue<Node> q;
char str[MAXN];void judgequeue(int x, int y) {Node tmp;if(x>=0 && x<m && y>=0 && y<n && g[x][y]==0) {tmp.x = x;tmp.y = y;q.push(tmp);}
}void bfs(int x, int y) {while(!q.empty())q.pop();Node cur;cur.x = x;cur.y = y;q.push(cur);while(!q.empty()) {Node tmp = q.front();q.pop();g[tmp.x][tmp.y] = 1;for(int i=0; i<8; ++i) {judgequeue(tmp.x+dir[i][0], tmp.y+dir[i][1]);}}
}int main(void) {char ch;int ans;while(scanf("%d%d", &m, &n)!=EOF && m) {memset(g, 0, sizeof(g));for(int i=0; i<m; ++i) {scanf("%s", str);for(int j=0; j<n; ++j) {ch = str[j];if(ch == '*')g[i][j] = 1;}}ans = 0;for(int i=0; i<m; ++i) {for(int j=0; j<n; ++j) {if(g[i][j] == 0) {ans++;bfs(i, j);}}}cout << ans << endl;}return 0;
}这篇关于hdu 1241 || poj 1562 Oil Deposits(搜索:BFS水题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
