제출 #1003270

#제출 시각아이디문제언어결과실행 시간메모리
1003270ulianamalanyakDijamant (COCI22_dijamant)C++14
70 / 70
201 ms51284 KiB
#include "bits/stdc++.h"

using namespace std;

#define endl '\n'
#define INF 1000000000000

typedef int ll;

const int DIM=2e3+7;

ll n,m;
int a[DIM][DIM];
int dp1[DIM][DIM];
int dp2[DIM][DIM];

int main()
{
    //freopen ("input.txt","r",stdin);
    //freopen ("output.txt","w",stdout);
    
    cin >> n >> m;

	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			char c;
			cin >> c;
			if (c=='#') a[i][j]=1;
		}
	}

	for (int i=1;i<=n;i++)
	{
		int cur=-1;
		for (int j=1;j<=m;j++)
		{
			if (a[i][j]==0) dp1[i][j]=-1;
			else
			{
				if (cur==-1) 
				{
					dp1[i][j]=j;
				}
				else if (cur==j-1)
				{
					dp1[i][j]=j;
				}
				else
				{
					if (dp1[i-1][j-1]==cur+1||(j-1==cur+1&&a[i-1][j-1]))
					{
						dp1[i][j]=cur;
					}
					else dp1[i][j]=j;
				}

				cur=j;
			}
		}
	}

	for (int i=n;i>=1;i--)
	{
		int cur=-1;
		for (int j=1;j<=m;j++)
		{
			if (a[i][j]==0) dp2[i][j]=-1;
			else
			{
				if (cur==-1) 
				{
					dp2[i][j]=j;
				}
				else if (cur==j-1)
				{
					dp2[i][j]=j;
				}
				else
				{
					if (dp2[i+1][j-1]==cur+1||(j-1==cur+1&&a[i+1][j-1]))
					{
						dp2[i][j]=cur;
					}
					else dp2[i][j]=j;
				}

				cur=j;
			}
		}
	}

	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			//cout << i << " " << j << " " << dp1[i][j] << " " << dp2[i][j] << endl;
		}
	}

	ll count=0;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			if (a[i][j]&&dp1[i][j]!=j&&dp2[i][j]!=j&&dp1[i][j]==dp2[i][j]) 
			{
				count++;
				//cout << i << " " << dp1[i][j] << " " << j << endl;
			}
		}
	}

	cout << count << endl;
  
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...