山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

AtCoder Beginner Contest 018 C - 菱型カウント

探索方法を工夫する

C - 菱型カウント

解法が思いつかなかったので、解説を読みました。

問題の概要については、下のサイトがうまく説明していました。

purple-jwl.hatenablog.com

解説を読んだらなるほどという解き方でしたが、僕には思いつきそうもありませんでした。

コード

import java.util.Scanner;

public class ProblemC {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int R = scan.nextInt();
        int C = scan.nextInt();
        int K = scan.nextInt();
        String[][] s = new String[R][C];
        for(int i = 0; i < R;  i++) {
            String t = scan.next();
            String []a = t.split("");
            for(int j = 0; j < C; j++) {
                s[i][j] = a[j];
            }
        }
        scan.close();
        int[][] a = new int[R][C];
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if(i == 0) {
                    if(s[i][j].equals("o")) {
                        a[i][j] = 1;
                    }else {
                        a[i][j] = 0;
                    }
                }else {
                    if(s[i][j].equals("o")) {
                        a[i][j] += a[i - 1][j] + 1;
                    }else {
                        a[i][j] = 0;
                    }
                }
            }
        }
        int[][] b = new int[R][C];
        for(int i = R - 1; i >= 0; i--) {
            for(int j = 0; j < C; j++) {
                if(i == R - 1) {
                    if(s[i][j].equals("o")) {
                        b[i][j] = 1;
                    }else {
                        b[i][j] = 0;
                    }
                }else {
                    if(s[i][j].equals("o")) {
                        b[i][j] += b[i + 1][j] + 1;
                    }else {
                        b[i][j] = 0;
                    }
                }
            }
        }
//     for(int i = 0; i < R; i++) {
//         for(int j = 0; j < C; j++) {
//             System.out.print(a[i][j] + "/" + b[i][j] + " ");
//         }
//         System.out.println();
//     }
        int cnt = 0;
        int flag = 0;
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                flag = 1;
                for(int k = 0; k <= K - 1; k++) {
                    if(j - k >= 0 && j + k <= C - 1) {
                        if((a[i][j + k] >= K - k && b[i][j + k] >= K - k
                                && a[i][j - k] >= K - k && b[i][j - k] >= K - k)) {
                            flag = 0;
                        }else {
                            flag = 1;
                            break;
                        }
                    }else {
                        flag = 1;
                        break;
                    }
                }
                if(flag == 0) {
                    //System.out.println((i + 1)+ " " + (j + 1));
                    cnt ++;
                }
            }
        }
        System.out.println(cnt);
    }
}