BFS。这里用了queue,以及在数据结构里存了上一个的高度。也可以递归调用完成BFS,在调用之前做判断:
import java.util.*;public class TopographicalImage{ public int[] calcPeakAreas(String[] topoData) { int m = topoData.length; int n = topoData[0].length(); ArrayListans = 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; }}