14391紙切れ

タイムアウトメモリコミット正解率2秒512 MB 40842227163855.582%

質問する

英善には数字が書かれた矩形の紙がある.紙は1×大きさの正方形の格子で、数字は各格子に書かれています.行は上から下へ、列は左から右へ.
英善は矩形を重ならない破片に切るつもりだ.それぞれが大きさが一つの長方形です.長さNのフラグメントはNビット数で表すことができる.横棒は左から連数、縦棒は上から下まで連数です.
図4×4紙を切る方法.

1枚当たりの合計は493+7160+23+58+9+45+91=7879であった.
紙を適当に切って、破片の和を最大にするプログラムを作成してください.

入力

第1行は、紙片の縦方向の大きさNおよび横方向の大きさMを与える.(1 ≤ N, M ≤ 4)
2行目から紙切れを渡します.1マスに書かれた数字は0から9の間の1つです.

しゅつりょく

英善が得られる点数の最値を出力する.

入力例1

2 3
123
312

サンプル出力1

435

入力例2

2 2
99
11

サンプル出力2

182

入力例3

4 3
001
010
111
100

サンプル出力3

1131

入力例4

1 1
8

サンプル出力4

8

コード#コード#

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

public class P_14391 {
    static int[]        wl;
    static int[][]      info;
    static int[][]      wid_or_len;
    static boolean[][]  visited;
    static int          max = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        wl = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        info = new int[wl[0]][wl[1]];
        for (int i = 0; i < wl[0]; i++) info[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
        wid_or_len = new int[wl[0]][wl[1]];
        visited = new boolean[wl[0]][wl[1]];

        piece_of_paper(0);
        bw.write(Integer.toString(max));
        bw.flush();
    }

    public static void piece_of_paper(int cnt) {
        if (cnt == wl[0] * wl[1]) {

            for (int i = 0 ; i < wl[0]; i++) Arrays.fill(visited[i], false);

            int result = find_max_score();
            max = (max > result) ? max : result;
        }
        else {
            wid_or_len[cnt / wl[1]][cnt % wl[1]] = 1;
            piece_of_paper(cnt + 1);

            wid_or_len[cnt / wl[1]][cnt % wl[1]] = 2;
            piece_of_paper(cnt + 1);
        }
    }

    public static int find_max_score() {
        int idx_i, idx_j;
        int num;
        int result = 0;

        for (int i = 0; i < wl[0]; i++) {
            for (int j = 0; j < wl[1]; j++) {

                idx_i = i;
                idx_j = j;
                num = 0;

                if (wid_or_len[idx_i][idx_j] == 1) {
                    while (wid_or_len[idx_i][idx_j] == 1 && visited[idx_i][idx_j] == false) {
                        num = num * 10 + info[idx_i][idx_j];
                        visited[idx_i][idx_j] = true;
                        idx_j++;
                        if (idx_j >= wl[1]) break;
                    }
                }
                else {
                    while (wid_or_len[idx_i][idx_j] == 2 && visited[idx_i][idx_j] == false) {
                        num = num * 10 + info[idx_i][idx_j];
                        visited[idx_i][idx_j] = true;
                        idx_i++;
                        if (idx_i >= wl[0]) break;
                    }
                }

                result += num;
            }
        }

        return result;
    }
}

コードの説明

各紙片は横紙片であってもよいし、縦紙片であってもよい.
したがって,1枚の紙を横紙に数え,1回,縦紙に1回,合計2回演算に関与する.
用紙の最大サイズは4×4=164\times4 = 164×4=16で、ポストトレースを使用する場合、最大演算量は2^16で、2秒を超えません.
この問題は,各紙片を横紙片と縦紙片に区別するほか,boolean値を有するアクセス配列を付加するために演算に追加のプロセスが必要である.
この追加のプロセスでは、16回をループし、値に影響を及ぼしたインデックスを参照するとtrueにアクセスし、演算に重複しないように制御します.
whileにも文を使用する方法があります.この場合、インデックスは非常に複雑になるため、ダブルfor文を使用し、idx i、idx j変数を使用して、文変数i、jとは独立します.
演算に参加すると、アクセスした[idx i][idx j]をtrueに変更し、紙片が横紙片(この場合wid or lenが1)であればidx jを増加させ、縦紙片(この場合wid or lenが0)であればidx iを増加させる.
そして、backtracking関数の終了条件cnt=wl[0]*wl[1]では、最後の演算を行う関数が呼び出され、アクセス関数が変更されるので、関数を呼び出す前に、アクセスする配列をすべてfalseに初期化する.初期化中にエラーが発生し続け、Arrays.fill(アクセス者、false)しか書かれていないため、二重配列を一度に初期化することはできません.二重配列の場合、for文で二次元部分を巡回し、Arraysを表示します.fillを使います.