求条ABC D
  • 板块学术版
  • 楼主lovely_hyzhuo
  • 当前回复6
  • 已保存回复6
  • 发布时间2024/1/20 21:58
  • 上次更新2024/1/21 09:40:33
查看原帖
求条ABC D
716099
lovely_hyzhuo楼主2024/1/20 21:58

rt

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
	int n,m,k;
	cin>>n>>m>>k;
//	vector<vector<char> >a(n+1)(m+1);
//	vector<vector<int> >dp(n+1)(m+1);
	char a[n+1][m+1];
	int dp[n+1][m+1];
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	int ans=0x7f7f7f7f;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			//cout<<1<<" "<<i<<" "<<j<<" "<<dp[i][j]<<endl;
			if(dp[i][j]!=0||a[i][j]=='x')
				continue;
			int mm=0;
			int ii=i,jj=j;
			int am=0,an=0;
			while(a[ii][j]!='x'&&ii<=n)
			{
				mm++;
				if(a[ii][j]=='o')
					am++;
				ii++;
			}
			ii=i-1;
			while(a[ii][j]!='x'&&!ii)
			{
				mm++;
				if(a[ii][j]=='o')
					am++;
				ii--;
			}
			int nn=0;
			ii=i,jj=j;
			while(a[i][jj]!='x'&&jj<=m)
			{
				nn++;
				if(a[i][jj]=='o')
					an++;
				jj++;
			}
			jj=j-1;
			while(a[i][jj]!='x'&&!jj)
			{
				nn++;
				if(a[i][jj]=='o')
					an++;
				jj--;
			}
			ii=i,jj=j;
			while(a[ii][j]!='x'&&ii<=n)
			{
				dp[ii][j]=min(dp[ii][j],mm-am);
				ii++;
			}
			ii=i-1;
			while(a[ii][j]!='x'&&!ii)
			{
				dp[ii][j]=min(dp[ii][j],mm-am);
				ii--;
			}
			ii=i,jj=j;
			while(a[i][jj]!='x'&&jj<=m)
			{
				dp[i][jj]=min(dp[ii][j],nn-an);
				jj++;
			}
			jj=j-1;
			while(a[i][jj]!='x'&&!jj)
			{
				dp[i][jj]=min(dp[ii][j],nn-an);
				jj--;
			}
			//nn--,mm--;
			cout<<i<<" "<<j<<" "<<nn<<" "<<an<<" "<<mm<<" "<<am<<" "<<ans<<endl;
			if(nn>=k&&mm>=k)
				ans=min(nn-an,min(mm-am,ans));
			else if(nn<k&&mm<k)
				continue;
			else if(nn>=k&&mm<k)
				ans=min(ans,nn-an);
			else
				ans=min(ans,mm-am);
			//cout<<i<<" "<<j<<" "<<ans<<endl;
		}
	}
	if(ans==0x7f7f7f7f||ans==k)
		cout<<"-1";
	else
		cout<<ans;
	return 0;
}
2024/1/20 21:58
加载中...