1125-Get Many Persimmon Trees
問題概要
WxHのマス目があり、そのうちN個が埋まっている。
そのN個の座標x,y(1<=x<=W,1<=y<=H)と整数S,T(1<=S<=W,1<=T<=H)が与えられた時、
SxTの大きさのマスに入る最大の埋まっているマスの個数を答えよ。
考え方
考えられる場所全てを調べる。
実装(C++)
#include <iostream> #include <cstring> using namespace std; char MAP[100][100]; int W,H,S,T,N; int main() { for(;cin>>N,N;){ cin>>W>>H; int x,y; memset(MAP,0,sizeof(MAP)); for(int i=0;i<N;i++){ cin>>x>>y; MAP[x-1][y-1]=1; } cin>>S>>T; int ans=0; for(int x=0;x<=W-S;x++){ for(int y=0;y<=H-T;y++){ int t=0; for(int i=0;i<S;i++){ for(int j=0;j<T;j++){ t+=MAP[i+x][y+j]; } } if(ans<t)ans=t; } } cout<<ans<<endl; } return 0; }