博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[topcoder]TopographicalImage
阅读量:5029 次
发布时间:2019-06-12

本文共 2374 字,大约阅读时间需要 7 分钟。

BFS。这里用了queue,以及在数据结构里存了上一个的高度。也可以递归调用完成BFS,在调用之前做判断:

import java.util.*;public class TopographicalImage{    public int[] calcPeakAreas(String[] topoData)    {        int m = topoData.length;        int n = topoData[0].length();        ArrayList
ans = new ArrayList
(); int total = 0; boolean[][] visited = new boolean[m][n]; while (total < m * n) { int max = -1; Pair p = new Pair(0, 0, 0); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (!visited[i][j] && topoData[i].charAt(j) > max) { max = topoData[i].charAt(j); p.x = i; p.y = j; p.lastHeight = max; } } } Queue
queue = new LinkedList
(); queue.add(p); int cnt = 0; while (queue.size() != 0) { Pair t = queue.poll(); int h = topoData[t.x].charAt(t.y); if (!visited[t.x][t.y] && h <= t.lastHeight) { visited[t.x][t.y] = true; cnt++; if (t.y + 1 < n) queue.add(new Pair(t.x, t.y + 1, h)); if (t.x + 1 < m) queue.add(new Pair(t.x + 1, t.y, h)); if (t.y - 1 >= 0) queue.add(new Pair(t.x, t.y - 1, h)); if (t.x - 1 >= 0) queue.add(new Pair(t.x - 1, t.y, h)); if (t.x + 1 < m && t.y + 1 < n) queue.add(new Pair(t.x + 1, t.y + 1, h)); if (t.x + 1 < m && t.y - 1 >= 0) queue.add(new Pair(t.x + 1, t.y - 1, h)); if (t.x - 1 >= 0 && t.y - 1 >= 0) queue.add(new Pair(t.x - 1, t.y - 1, h)); if (t.x - 1 >= 0 && t.y + 1 < n) queue.add(new Pair(t.x - 1, t.y + 1, h)); } } ans.add(cnt); total += cnt; } int[] res = new int[ans.size()]; for (int i = 0; i < ans.size(); i++) { res[i] = ans.get(i); } return res; }} class Pair{ int x; int y; int lastHeight; public Pair(int _x, int _y, int _lastHeight) { x = _x; y = _y; lastHeight = _lastHeight; }}

  

转载于:https://www.cnblogs.com/lautsie/p/3359885.html

你可能感兴趣的文章
c# aop讲解
查看>>
iterable与iterator
查看>>
返回顶部(动画)
查看>>
webpack+react+antd 单页面应用实例
查看>>
Confluence 6 SQL Server 数据库驱动修改
查看>>
Confluence 6 通过 SSL 或 HTTPS 运行 - 备注和问题解决
查看>>
【47.76%】【Round #380B】Spotlights
查看>>
Git(使用码云)
查看>>
分享Java web 开发必游之路
查看>>
IIS初始化(预加载),解决第一次访问慢,程序池被回收问题(转载)
查看>>
Bean的Scope
查看>>
【BZOJ】3142: [Hnoi2013]数列
查看>>
http初探
查看>>
W3C标准以及规范
查看>>
1. Change the emulator screen size
查看>>
[React] React Fundamentals: State Basics
查看>>
[leetcode] Distinct Subsequences
查看>>
Could not launch “PushTest.app”
查看>>
HDU 2147 (博弈) kiki's game
查看>>
何为抓包?
查看>>