网站友情链接如何做/网站广告策划

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1241

题目的意思很简单，问你有多少块油田。。‘@’表示油田，‘*’表示不是油田。。连在一起的油田属于同一个油田。。八个方向相邻被称为连在一起。。

直接bfs或dfs都行。。时间复杂度为O(m)。m为‘@’个数。。

分别用dfs和bfs实现了一下。。时间差不多。。原因吗？都是走过以后就不用在走了。。

bfs Code:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;const int N = 1e2 + 5;
const int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
const int dy[] = {1, -1, -1, 0, 1, -1, 0, 1};
int n, m;
char map[N][N];struct Node
{int x, y;Node() {}Node(int a, int b){x = a;y = b;}
};void bfs(int bx, int by)
{queue<Node> q;q.push(Node(bx, by));map[bx][by] = '*';while(!q.empty()){Node tmp = q.front(), tmp1;q.pop();for(int i = 0 ; i < 8; i ++){tmp1.x = tmp.x + dx[i]; tmp1.y = tmp.y + dy[i];if(tmp1.x < 1 || tmp1.x > n || tmp1.y < 1 || tmp1.y > m || map[tmp1.x][tmp1.y] == '*') continue;q.push(tmp1);map[tmp1.x][tmp1.y] = '*';}}return ;
}int main()
{while(scanf("%d %d", &n, &m) && (n || m)){getchar();for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++)scanf("%c", &map[i][j]);getchar();}int ans = 0;for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++)if(map[i][j] == '@') {bfs(i, j); ans ++;}}cout << ans << endl;}return 0;
}

dfs Code：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;const int N = 105;
const int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
const int dy[] = {1, -1, -1, 0, 1, -1, 0, 1};
char map[N][N];
int n, m;void dfs(int x, int y)
{
//    cout << "now = " << x << ' ' << y << endl;for(int i = 0; i < 8; i ++){int gox = x + dx[i], goy = y + dy[i];if(gox < 1 || gox > n || goy < 1 || goy > m || map[gox][goy] == '*') continue;map[gox][goy] = '*';dfs(gox, goy);}return ;
}int main()
{
//    freopen("1.txt", "r", stdin);while(scanf("%d %d", &n, &m) && (n || m)){getchar();for(int i = 1;  i <= n; i ++){for(int j = 1; j <= m; j ++)scanf("%c", &map[i][j]);getchar();}int ans = 0;for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){if(map[i][j] == '@'){map[i][j] = '*';dfs(i, j);ans ++;}}}cout << ans << endl;}return 0;
}