t8m8-mem8

競プロとか、学んだことを書いていきます。

AOJ 1174: Identically Colored Panels Connection

AOJ-ICPCの350を埋めようと思う。

問題

Identically Colored Panels Connection | Aizu Online Judge

解法

パネルの変更の仕方を全探索する。実装でハマらなければ簡単。
DFSでカウントしていったけどBFSのほうが楽だった気がする。

import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class AOJ1174 {

    static final Scanner in = new Scanner(System.in);
    static final PrintWriter out = new PrintWriter(System.out,false);
    static boolean debug = false;

    static int h, w, c;
    static int[] change;
    static int[][] p, stamp;

    static int[] dx = { 0, 1, 0,-1};
    static int[] dy = { 1, 0,-1, 0};

    static int rec(int y, int x, int pos) {
        int res = stamp[y][x] == 6 ? 1 : 0;
        stamp[y][x] = pos;
        for (int k=0; k<4; k++) {
            int ny = y + dy[k];
            int nx = x + dx[k];
            if (ny < 0 || nx < 0 || h <= ny || w <= nx) continue;
            int ptmp = pos;
            while (ptmp < 6 && change[ptmp] != p[ny][nx]) ptmp++;
            if (stamp[ny][nx] <= ptmp) continue;
            res += rec(ny, nx, ptmp);
        }
        return res;
    }

    static boolean solve() {
        h = in.nextInt();
        w = in.nextInt();
        c = in.nextInt();
        if (h + w + c == 0) return false;

        p = new int[h][w];

        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                p[i][j] = in.nextInt();
            }
        }

        int ans = 0;

        for (int i=1; i<=6; i++) {
            for (int j=1; j<=6; j++) {
                for (int k=1; k<=6; k++) {
                    for (int l=1; l<=6; l++) {
                        change = new int[]{p[0][0], i, j, k, l, c};

                        stamp = new int[h][w];
                        for (int m=0; m<h; m++) {
                            Arrays.fill(stamp[m],6);
                        }
                        ans = Math.max(ans, rec(0, 0, 0));
                    }
                }
            }
        }

        out.println(ans);

        return true;
    }

    public static void main(String[] args) {
        debug = args.length > 0;
        long start = System.currentTimeMillis();

        while(solve());
        out.flush();

        long end = System.currentTimeMillis();
        dump((end-start) + "ms");
        in.close();
        out.close();
    }

    static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}
広告を非表示にする