| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 116109 | faustaadp | Dango Maker (JOI18_dango_maker) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,m,i,j,has,te;
char a[3030][3030];
int x[9000010];
int b[9000010];
int mat[9000010];
vector<int> v[9000010];
ll dfs(ll aa)
{
if(b[aa]==i)
return 0;
b[aa]=1;
ll ii;
for(ii=0;ii<v[aa].size();ii++)
if(mat[v[aa][ii]]==-1||dfs(v[aa][ii]))
{
mat[v[aa][ii]]=aa;
return 1;
}
return 0;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
p[(i-1)*m+j]=(i-1)*m+j;
cin>>a[i][j];
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(j+2<=m&&a[i][j]=='R'&&a[i][j+1]=='G'&&a[i][j+2]=='W')
{
te++;
has++;
x[(i-1)*m+j]=te;
x[(i-1)*m+j+1]=te;
x[(i-1)*m+j+2]=te;
}
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(i+2<=n&&a[i][j]=='R'&&a[i+1][j]=='G'&&a[i+2][j]=='W')
{
te++;
has++;
if(x[(i-1)*m+j]!=0)
{
v[te].pb(x[(i-1)*m+j]);
}
if(x[(i)*m+j]!=0)
{
v[te].pb(x[(i)*m+j]);
}
if(x[(i+1)*m+j]!=0)
{
v[te].pb(x[(i+1)*m+j]);
}
}
}
memset(mat,-1,sizeof(mat));
for(i=1;i<=te;i++)
{
has-=dfs(i);
}
cout<<has<<"\n";
}