2030 The Secret Number

※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

2030 The Secret Number

問題

解答方針

典型的な動的計画法で解ける.

二次元配列valtable(valtable[i][j]はi行j列を末尾とする数字の最大値)を左上から埋めていく.その際の基本式は
//table[i][j] 入力のi行j列の文字
//valtable[i][j] i行j列を末尾とする数字の最大値

if(table[i][j]が数字) then
  valtable[i][j] = max(valtable[i][j-1],valtable[i-1][j])*10 + table[i][j]の値;
else
  valtable[i][j] = 0;
である.i=0やj=0の場合は例外的に処理する必要があることに注意する.

なお,掛け算,足し算をBigIntegerで行っているのは勿論実行効率が悪く,文字列処理によって実現すべきだが,今回は楽をすることを優先させてみた.

解答例

import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true){
            int w = sc.nextInt();
            int h = sc.nextInt();
            if(w==0&&h==0) break;
            char[][] table = new char[h][w];
            for(int i=0;i<h;i++){
                String line = sc.next();
                table[i] = line.toCharArray();
            }
            Solver sol = new Solver(w,h,table);
            System.out.println(sol.solve());
        }
    }
}

class Solver{
    int w;
    int h;
    char[][] table;
    BigInteger[][] valtable;
    Solver(int sw,int sh,char[][] stable){
        w = sw;
        h = sh;
        table = stable;
        valtable = new BigInteger[h][w];
    }
    public BigInteger solve(){
        for(int i=0;i<Math.min(h,w);i++){
            compute(i,i);
            for(int j=i+1;j<w;j++) compute(i,j);
            for(int j=i+1;j<h;j++) compute(j,i);
        }
        
        BigInteger ret = BigInteger.ZERO;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                ret = ret.max(valtable[i][j]);
            }
        }
        return ret;
    }
    public void compute(int i,int j){
        if(!isDisit(table[i][j])) valtable[i][j] = BigInteger.ZERO;
        else{
            if(i>0&&j>0){
                valtable[i][j] = (valtable[i-1][j].max(valtable[i][j-1]))
                    .multiply(BigInteger.TEN).add(new BigInteger(Character.toString(table[i][j])));
            }
            else if(i>0){
                valtable[i][j] = valtable[i-1][j]
                    .multiply(BigInteger.TEN).add(new BigInteger(Character.toString(table[i][j])));
            }
            else if(j>0){
                valtable[i][j] = valtable[i][j-1]
                    .multiply(BigInteger.TEN).add(new BigInteger(Character.toString(table[i][j])));
            }
            else{
                valtable[i][j] = new BigInteger(Character.toString(table[i][j]));
            }
        }
    }
    public static boolean isDisit(char c){
        if('0'<=c&&c<='9') return true;
        else return false;
    }
}
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。