14500 테트로미노

https://www.acmicpc.net/problem/14500

브루트 포스로 모든 좌표에 대하여 테트로미노의 모든 경우의 수인 19가지를 살펴보면 된다. 탐색 횟수가 최대 500*500*19*4=19000000 이므로 시간 내에 충분히 돌아간다.

#include <cstdio>
#include <algorithm>
using namespace std;
 
int n,m,map[510][510],ans;
pair<int,int> d[19][4]={
    {{0,0},{0,1},{0,2},{0,3}},
    {{0,0},{1,0},{2,0},{3,0}},
    {{0,0},{0,1},{1,0},{1,1}},
    {{0,0},{1,0},{2,0},{2,1}},
    {{0,0},{0,1},{0,2},{1,0}},
    {{0,0},{0,1},{1,1},{2,1}},
    {{0,0},{0,1},{0,2},{-1,2}},
    {{0,0},{1,0},{1,1},{2,1}},
    {{0,0},{0,1},{-1,1},{-1,2}},
    {{0,0},{0,1},{0,2},{1,1}},
    {{0,0},{0,1},{-1,1},{1,1}},
    {{0,0},{0,1},{0,2},{-1,1}},
    {{0,0},{1,0},{2,0},{1,1}},
    {{0,0},{1,0},{2,0},{2,-1}},
    {{0,0},{1,0},{1,1},{1,2}},
    {{0,0},{0,1},{1,0},{2,0}},
    {{0,0},{0,1},{0,2},{1,2}},
    {{0,0},{1,0},{0,1},{-1,1}},
    {{0,0},{0,1},{1,1},{1,2}}
};
 
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&map[i][j]);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            for(int k=0;k<19;k++)
            {
                int sum=0;
                bool flag=true;
                for(int l=0;l<4;l++)
                {
                    int nx=i+d[k][l].first,ny=j+d[k][l].second;
                    if(nx<0 || nx>=n || ny<0 || ny>=m)
                    {
                        flag=false;
                        break;
                    }
                    sum+=map[nx][ny];
                }
                if(flag && ans<sum) ans=sum;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}