탐색 최적화보다는 구현이 중심인 문제입니다.

각 테트로미노에 대해서 확인해야 할 좌표를 전처리해두고 합의 최댓값을 구했습니다.

코드
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]
    }
}