首页 > 代码库 > AOJ 0118 Property Distribution【DFS】
AOJ 0118 Property Distribution【DFS】
题意：
在H * W的矩形果园里有苹果、梨、蜜柑三种果树， 相邻（上下左右）的同种果树属于同一个区域，给出果园的果树分布，求总共有多少个区域。
输入：
多组数据，每组数据第一行为两个整数H，W（H <= 100, W <= 100）， H =0 且 W = 0代表输入结束。以下H行W列表示果园的果树分布， 苹果是@，梨是#， 蜜柑是*。
输出：
对于每组数据，输出其区域的个数。
#include<cstdio>#include<vector>#include<queue>#include<string>#include<map>#include<iostream>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int INF = 0x7FFFFFFF;const int maxn = 1e5 + 10; #define MAX_W 100#define MAX_H 100char farm[MAX_W][MAX_H];int W, H;const int direction[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 },}; void dfs(int x, int y, char tree){ farm[x][y] = ‘x‘; for (int i = 0; i < 4; ++i) { int nx = x + direction[i][0]; int ny = y + direction[i][1]; if (nx >= 0 && nx < W && ny >= 0 && ny < H && farm[nx][ny] == tree) { dfs(nx, ny, tree); } }} int main(){ while (cin >> H >> W, W > 0) { int res = 0; int x, y; for (y = 0; y < H; ++y) { for (x = 0; x < W; ++x) { cin >> farm[x][y]; } } for (y = 0; y < H; ++y) { for (x = 0; x < W; ++x) { if (farm[x][y] != ‘x‘) { dfs(x, y, farm[x][y]); ++res; } } } cout << res << endl; } return 0;}AOJ 0118 Property Distribution【DFS】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。