B - Find Symmetries AtCoder Grand Contest 023

B - Find Symmetries

問題

N*Nのアルファベットが与えられる。

上にa、右にb動かしたら対称になるようなa,bの数を求めよ

制約

• $1\le N\le 300$
• $S_{i,j}$ ( $1\le i,j\le N$ ) は英小文字

解法

対称なものを上下にa動かした物も対称である。

対称でないものを動かした場合もそう。

つまりa,bのとり方をN＾２回調べる必要はなく、N回見ればいい

public static void main(String[] args)
{
    //longを忘れるなオーバーフローするぞ
    N = sc.nextInt();
    map = sc.nextCharArray2(N, N);
    if (all())
    {
        System.out.println(N * N);
        return;
    }
    //1ならよい盤面 0ならダメ
    dp = new int[N][N];
    fill(dp, -1);
    for (int ai = 0; ai < N; ai++)
    {
        for (int bi = 0; bi < N; bi++)
        {
            if (dp[ai][bi] != -1) continue;
            if (check(ai, bi)) fslash(ai, bi, 1);
            else fslash(ai, bi, 0);
        }
    }
    long res = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if(dp[i][j] ==1)res++;
        }
    }
    System.out.println(res);
}

public static void fslash(int a, int b, int v)
{
    while (true)
    {
        if (dp[a][b] != -1) break;
        dp[a][b] = v;
        a++;
        b++;
        a %= N;
        b %= N;
    }
}

//good ならtrue
public static boolean check(int a, int b)
{
    for (int hi = 0; hi < N; hi++)
    {
        for (int wi = hi + 1; wi < N; wi++)
        {
            int nh = hi + a;
            int nw = wi + b;
            int rh = wi + a;
            int rw = hi + b;
            nh %= N;
            nw %= N;
            rh %= N;
            rw %= N;
            if (map[nh][nw] != map[rh][rw]) return false;
        }
    }
    return true;
}

public static boolean all()
{
    char c = map[0][0];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (map[i][j] != c) return false;
        }
    }
    return true;
}