[白俊]#14391紙切れ
27047 ワード
質問する
英善には数字が書かれた矩形の紙がある.紙は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.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static int sum;
static int N;
static int M;
static boolean[][] visited;
static char[][] map;
static StringBuilder sb;
static int max = Integer.MIN_VALUE;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
M = Integer.parseInt(input[1]);
map = new char[N][M];
for(int i=0; i<N; i++) {
String str = br.readLine();
for(int j=0; j<M; j++)
map[i][j] = str.charAt(j);
}
bitmask(0, 0, new int[N][M]);
System.out.println(max);
}
public static void bitmask(int x, int y, int[][] bitmap) {
for(int i=0; i<2; i++) { //가로는 1, 세로는 0 으로 비트마스킹
if(y==M) {
if(x==N-1) {
sol(bitmap);
break;
}
x=x+1;
y=0;
}
bitmap[x][y] = i;
bitmask(x, y+1, bitmap);
}
}
public static void sol(int[][] bitmap) {
visited = new boolean[N][M];
sum = 0;
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(!visited[i][j]) {
visited[i][j] = true;
dfs(i, j, bitmap);
}
}
}
max = Math.max(max, sum);
}
public static void dfs(int x, int y, int[][] bitmap) { //비트마스킹대로 숫자 더 함
sb = new StringBuilder();
sb.append(map[x][y]);
if(bitmap[x][y]==0) {
int nx = x+1;
int ny = y;
while(nx<N && bitmap[x][y]==bitmap[nx][ny]) {
if(visited[nx][ny]) continue;
visited[nx][ny] = true;
sb.append(map[nx][ny]);
nx++;
}
nx = x-1;
while(nx>=0 && bitmap[x][y]==bitmap[nx][ny]) {
if(visited[nx][ny]) continue;
visited[nx][ny] = true;
sb.insert(0, map[nx][ny]);
nx--;
}
}
else {
int nx = x;
int ny = y+1;
while(ny<M && bitmap[x][y]==bitmap[nx][ny]) {
if(visited[nx][ny]) continue;
visited[nx][ny] = true;
sb.append(map[nx][ny]);
ny++;
}
ny = y-1;
while(ny>=0 && bitmap[x][y]==bitmap[nx][ny]) {
if(visited[nx][ny]) continue;
visited[nx][ny] = true;
sb.insert(0, map[nx][ny]);
ny--;
}
}
sum += Integer.parseInt(sb.toString());
}
}
Reference
この問題について([白俊]#14391紙切れ), 我々は、より多くの情報をここで見つけました https://velog.io/@pss407/백준14391-종이-조각テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol