| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 884953 | maxFedorchuk | Dango Maker (JOI18_dango_maker) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const long long MX=2020;
long long mtr[MX][MX];
char ch[MX][MX];
const long long MXK=MX*MX;
vector < long long > mas[2*MXK];
long long usea[2*MXK];
long long pr[2*MXK];
long long timer=0,koma,komb;
bool khuna(long long zar)
{
if(usea[zar])
{
return 0;
}
usea[zar]=1;
for(auto u:mas[zar])
{
if(pr[u]==0)
{
pr[zar]=u;
pr[u]=zar;
return 1;
}
}
for(auto u:mas[zar])
{
if(khuna(pr[u]))
{
pr[zar]=u;
pr[u]=zar;
return 1;
}
}
return 0;
}
void kntkhuna()
{
while(true)
{
fill(usea+1,usea+1+timer,0);
bool p=0;
for(long long i=1;i<=koma;i++)
{
if(pr[i]==0)
{
if(khuna(i))
{
p=1;
}
}
}
if(!p)
{
return;
}
}
return;
}
void DFS(long long zar)
{
usea[zar]=1;
if(zar<=koma)
{
for(auto u:mas[zar])
{
if(pr[u]!=zar && usea[u]==0)
{
DFS(u);
}
}
}
else
{
if(usea[pr[zar]]==0)
{
DFS(pr[zar]);
}
}
return;
}
int main()
{
cin.tie(0);
ios_base::sync_with_stdio(0);
long long n,m;
cin>>n>>m;
for(long long i=1;i<=n;i++)
{
for(long long j=1;j<=m;j++)
{
cin>>ch[i][j];
}
}
for(long long i=1;i<=n;i++)
{
for(long long j=1;(j+2)<=m;j++)
{
if(ch[i][j]=='R' && ch[i][j+1]=='G' && ch[i][j+2]=='W')
{
timer++;
mtr[i][j]=timer;
}
}
}
koma=timer;
for(long long i=1;(i+2)<=n;i++)
{
for(long long j=1;j<=m;j++)
{
if(ch[i][j]=='R' && ch[i+1][j]=='G' && ch[i+2][j]=='W')
{
timer++;
for(long long corx=i;corx<=(i+2);corx++)
{
for(long long cory=max(1,j-2);cory<=j;cory++)
{
if(mtr[corx][cory])
{
mas[mtr[corx][cory]].push_back(timer);
mas[timer].push_back(mtr[corx][cory]);
}
}
}
}
}
}
komb=timer-koma;
if(koma==0)
{
cout<<komb<<"\n";
return 0;
}
if(komb==0)
{
cout<<koma<<"\n";
return 0;
}
kntkhuna();
fill(usea+1,usea+koma+komb+1,0);
for(long long i=1;i<=koma;i++)
{
if(pr[i]==0)
{
DFS(i);
}
}
long long res=0;
for(long long i=1;i<=koma;i++)
{
res+=(usea[i]==1);
}
for(long long i=(koma+1);i<=(koma+komb);i++)
{
res+=(usea[i]==0);
}
cout<<res<<"\n";
return 0;
}