탐색 최적화보다는 구현이 중심인 문제입니다.
각 테트로미노에 대해서 확인해야 할 좌표를 전처리해두고 합의 최댓값을 구했습니다.
코드
use std::io::{stdin, Read};
static TETROMINOES: [[(usize, usize); 4]; 19] = [
// I
[(0, 0), (0, 1), (0, 2), (0, 3)],
[(0, 0), (1, 0), (2, 0), (3, 0)],
// O
[(0, 0), (0, 1), (1, 0), (1, 1)],
// L
[(0, 0), (1, 0), (2, 0), (2, 1)],
[(1, 0), (1, 1), (1, 2), (0, 2)],
[(0, 0), (0, 1), (1, 1), (2, 1)],
[(0, 0), (1, 0), (0, 1), (0, 2)],
// J
[(0, 1), (1, 1), (2, 1), (2, 0)],
[(0, 0), (0, 1), (0, 2), (1, 2)],
[(0, 0), (1, 0), (2, 0), (0, 1)],
[(0, 0), (1, 0), (1, 1), (1, 2)],
// S
[(0, 1), (1, 1), (1, 0), (0, 2)],
[(0, 0), (1, 0), (1, 1), (2, 1)],
// Z
[(0, 0), (0, 1), (1, 1), (1, 2)],
[(0, 1), (1, 1), (1, 0), (2, 0)],
// T
[(0, 0), (0, 1), (0, 2), (1, 1)],
[(0, 0), (1, 0), (2, 0), (1, 1)],
[(0, 1), (1, 0), (1, 1), (1, 2)],
[(0, 1), (1, 1), (2, 1), (1, 0)],
];
fn main() {
let mut input = String::new();
stdin().read_to_string(&mut input).unwrap();
let mut input = input.split_ascii_whitespace().map(str::parse).flatten();
let n = input.next().unwrap();
let m = input.next().unwrap();
let grid = Matrix(input.take(n * m).collect(), m);
let mut max = 0;
for r in 0..n {
for c in 0..m {
'mino: for tetromino in &TETROMINOES {
let mut count = 0;
for &(dr, dc) in tetromino {
if r + dr < n && c + dc < m {
count += grid[r + dr][c + dc];
} else {
continue 'mino;
}
}
max = max.max(count);
}
}
}
println!("{}", max);
}
struct Matrix<T>(Vec<T>, usize);
impl<T> std::ops::Index<usize> for Matrix<T> {
type Output = [T];
fn index(&self, index: usize) -> &Self::Output {
&self.0[index * self.1..][..self.1]
}
}
impl<T> std::ops::IndexMut<usize> for Matrix<T> {
fn index_mut(&mut self, index: usize) -> &mut Self::Output {
&mut self.0[index * self.1..][..self.1]
}
}