Educational Codeforces Round 1 D. Igor In the Museum
原题:http://codeforces.com/contest/598/problem/D
题目大意: 给一个图, 点(.) 是人可以待的位置, 星号(*) 是墙壁, 找出点和星号相邻的可能有多少个.
分析: 上来flood fill, 秒挂testcase 10, 加了visited[][] 秒挂testcase15, 后来发现里面重复请求非常多 真是!@#@!#!, 于是记录一下每次请求的结果. 原想是用uf记录, 后来想了想有现成的k, 就用k记录了…一个hashmap来的比uf方便的多.
public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int m = in.readInt(); int k = in.readInt(); char[][] map = new char[n][m]; int[][] visited = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { map[i][j] = in.readCharacter(); } } Map<Integer,Integer> list = new HashMap<>(); //记录一下已经算过的 for (int i = 0; i < k; i++) { int t1 = in.readInt() - 1; int t2 = in.readInt() - 1; if (visited[t1][t2] > 0) {//如果已经算过了, 找出第几次算的答案 out.printLine(list.get(visited[t1][t2])); } else {//如果没算过 int ans = solve(map, t1, t2, visited, i + 1);//从1开始到k, 每次 out.printLine(ans); list.put(i+1,ans);//记录一下算的结果 } } } private int solve(char[][] map, int i, int j, int[][] visited, int id) { Queue<Pair<Integer, Integer>> queue = new LinkedList<>(); queue.add(Pair.makePair(i, j)); int count = 0; while (!queue.isEmpty()) { Pair<Integer, Integer> cur = queue.poll(); if (visited[cur.first][cur.second] > 0) { continue; } visited[cur.first][cur.second] = id; if (map[cur.first + 1][cur.second] == '.') { queue.add(Pair.makePair(cur.first + 1, cur.second)); } else { count++; } if (map[cur.first - 1][cur.second] == '.') { queue.add(Pair.makePair(cur.first - 1, cur.second)); } else { count++; } if (map[cur.first][cur.second + 1] == '.') { queue.add(Pair.makePair(cur.first, cur.second + 1)); } else { count++; } if (map[cur.first][cur.second - 1] == '.') { queue.add(Pair.makePair(cur.first, cur.second - 1)); } else { count++; } } return count; }
Leave A Comment