首页 > 代码库 > UVa 11094 - Continents
UVa 11094 - Continents
题目:有一些岛屿在湖中。地图用两种字符表示。当前处在位置是一个岛屿。求除了当前岛屿外的最大岛屿。
分析:图论,floodfill。直接利用dfs求联通部分的面积就可以,然后取出最大。
说明:横线没有边界,初始的岛屿不算在内。
╮(╯▽╰)╭。
#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> using namespace std; char maps[22][22]; int dxy[4][2] = {0,1,1,0,-1,0,0,-1}; int dfs(int x, int y, int m, int n, char c) { if (x < 0 || x >= m) return 0; if (maps[x][y] != c) return 0; maps[x][y] = 0; int sum = 1; for (int i = 0; i < 4; ++ i) sum += dfs(x+dxy[i][0], (y+n+dxy[i][1])%n, m, n, c); return sum; } int main() { int m,n,x,y; while (cin >> m >> n) { for (int i = 0; i < m; ++ i) cin >> maps[i]; cin >> x >> y; char ch = maps[x][y]; int Max = 0; dfs(x, y, m, n, ch); for (int i = 0; i < m; ++ i) for (int j = 0; j < n; ++ j) if (maps[i][j] == ch) Max = max(Max, dfs(i, j, m, n, ch)); cout << Max << endl; } return 0; }
UVa 11094 - Continents
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。