코드포스 611C (codeforces 611C)

코드포스 611C (codeforces 611C) 문제 풀이 및 코드 (description and code)

목차

Problem - 611C - Codeforces

코드

import java.io.*;
import java.util.Arrays;

public class CF611C {
    static int h, w, q, r1, r2, c1, c2;
    static char[][] map = new char[501][501];
    static int[][][] m = new int[2][501][501];
    static String ins[], in;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        ins = br.readLine().split(" ");
        h = Integer.parseInt(ins[0]);
        w = Integer.parseInt(ins[1]);
        for (int i = 1; i <= h; i++) {
            in = br.readLine();
            for (int j = 1; j <= w; j++) {
                map[i][j] = in.charAt(j - 1);
            }
        }
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j <= h; j++) {
                Arrays.fill(m[i][j], -1);
            }
        }
        for (int i = 1; i <= h; i++) {
            dpc(i, w);
        }
        for (int i = 1; i <= w; i++) {
            dpr(h, i);
        }


        q = Integer.parseInt(br.readLine());
        for (int i = 0; i < q; i++) {
            ins = br.readLine().split(" ");
            r1 = Integer.parseInt(ins[0]);c1 = Integer.parseInt(ins[1]);
            r2 = Integer.parseInt(ins[2]);c2 = Integer.parseInt(ins[3]);
            bw.write(sum(r1, c1, r2, c2) + "\n");bw.flush();
        }
        bw.close();
    }
    public static int dpc(int r, int c) {
        if (c == 1) return 0;
        else if (m[0][r][c] != -1) return m[0][r][c];
        else {
            m[0][r][c] = 0;
            m[0][r][c] += dpc(r, c - 1) +
                    ((map[r][c - 1] == '.' && map[r][c] == '.') ? 1 : 0);

            return m[0][r][c];
        }
    }
    public static int dpr(int r, int c) {
        if (r == 1) return 0;
        else if (m[1][r][c] != -1) return m[1][r][c];
        else {
            m[1][r][c] = 0;

            m[1][r][c] += dpr(r - 1, c) +
                    ((map[r - 1][c] == '.' && map[r][c] == '.') ? 1 : 0);

            return m[1][r][c];
        }
    }
    public static int sum(int r1, int c1, int r2, int c2) {
        int s1 = 0, s2 = 0;
        for (int i = r1; i <= r2; i++) {
            int c2sum = m[0][i][c2] < 0 ? 0 : m[0][i][c2];
            int c1sum = m[0][i][c1] < 0 ? 0 : m[0][i][c1];
            s1 += c2sum - c1sum;
        }
        for (int i = c1; i <= c2; i++) {
            int r2sum = m[1][r2][i] < 0 ? 0 : m[1][r2][i];
            int r1sum = m[1][r1][i] < 0 ? 0 : m[1][r1][i];
            s2 += r2sum - r1sum;
        }
        return s1 + s2;
    }
}

설명

Copied to clipboard