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;
    }