Vin Diagrams

C++(g++ 7.5.0)(g++7.5.0) 解法, 执行用时: 3ms, 内存消耗: 452K, 提交时间: 2022-11-14 02:07:52

#include<iostream>
#include<queue>
using namespace std;
const int N = 1e2 + 5;
const int dx[4]{ 0,0,-1,1 }, dy[4]{ -1,1,0,0 };
int r, c, ans1, ans2, ans3, ans4, vis[N][N], ai, aj, bi, bj;
char g[N][N];

bool check1(int i, int j)
{
	return g[i - 1][j] == 'X' && g[i + 1][j] == 'X' && g[i][j - 1] == 'X' && g[i][j + 1] == 'X' && g[i - 1][j - 1] == '.' && g[i - 1][j + 1] == '.' && g[i + 1][j - 1] == '.' && g[i + 1][j + 1] == '.';
}

struct Node
{
	int x, y;
};

pair<int, char> bfs(int x, int y)
{
	pair<int, char> ret = { 1,'O' };
	queue<Node> q;
	q.push({ x,y});
	vis[x][y] = 1;
	while (q.size())
	{
		auto top = q.front();
		q.pop();
		for (int i = 0; i <= 3; ++i)
		{
			auto [nx, ny] = top;
			nx += dx[i], ny += dy[i];
			if (g[nx][ny] == '\0')
			{
				return { 0,'\0' };
			}
			if (g[nx][ny] == 'A' && ret.second == 'O')
			{
				ret.second = 'A';
			}
			if(g[nx][ny] == 'B' && ret.second == 'O')
			{
				ret.second = 'B';
			}
			if (vis[nx][ny] == 0 && g[nx][ny] == '.')
			{
				++ret.first;
				q.push({ nx,ny});
				vis[nx][ny] = 1;
			}
		}
	}
	return ret;
}

void brush(char c)
{
	int i, j;
	if (c == 'A')
	{
		i = ai, j = aj;
	}
	if (c == 'B')
	{
		i = bi, j = bj;
	}
	queue<Node> q;
	q.push({ i,j });
	while (q.size())
	{
		auto top = q.front();
		q.pop();
		for (int k = 0; k <= 3; ++k)
		{
			int nx = top.x + dx[k], ny = top.y + dy[k];
			if (g[nx][ny] == 'X')
			{
				g[nx][ny] = c;
				q.push({ nx,ny });
			}
			if (g[nx][ny] == 'O')
			{
				nx = nx + dx[k], ny = ny + dy[k];
				if (g[nx][ny] == 'X')
				{
					g[nx][ny] = c;
					q.push({ nx,ny });
				}
			}
		}
	}
}

void gg(const pair<int, char>& tmp)
{
	if (tmp.second == 'A')
	{
		ans1 = tmp.first;
	}
	else if (tmp.second == 'B')
	{
		ans2 = tmp.first;
	}
	else if (tmp.second == 'O')
	{
		ans3 = tmp.first;
	}
}

void solve()
{
	cin >> r >> c;
	for (int i = 1; i <= r; ++i)
	{
		for (int j = 1; j <= c; ++j)
		{
			cin >> g[i][j];
			if (g[i][j] == 'A')
			{
				ai = i, aj = j;
				g[i][j] = 'X';
			}
			if (g[i][j] == 'B')
			{
				bi = i, bj = j;
				g[i][j] = 'X';
			}
		}
	}
	int x, y;
	for (int i = 1; i <= r; ++i)
	{
		for (int j = 1; j <= c; ++j)
		{
			if (g[i][j] == 'X')
			{
				if (check1(i, j))
				{
					g[i][j] = 'O';
					x = i, y = j;
				}
			}
		}
	}

	//cout << '\n';
	brush('A');
	brush('B');
	/*for (int i = 1; i <= r; ++i)
	{
		for (int j = 1; j <= c; ++j)
		{
			cout << g[i][j];
			if (j == c)
			{
				cout << '\n';
			}
		}
	}*/
	auto tmp = bfs(x - 1, y - 1);
	ans1 = tmp.first;

	tmp = bfs(x - 1, y + 1);
	ans2 = tmp.first;

	tmp = bfs(x + 1, y - 1);
	ans3 = tmp.first;

	tmp = bfs(x + 1, y + 1);
	ans4 = tmp.first;
	int last1, last2, last3;
	last1 = last2 = last3 = 0;

	//1 * 2
	//* * *
	//3 * 4

	if (ans1 == 0)
	{
		last3 = ans4;
		if (g[x][y - 1] == 'A')
		{
			last1 = ans3;
			last2 = ans2;
		}
		else
		{
			last1 = ans2;
			last2 = ans3;
		}
	}
	else if (ans2 == 0)
	{
		last3 = ans3;
		if (g[x][y + 1] == 'A')
		{
			last1 = ans4;
			last2 = ans1;
		}
		else
		{
			last1 = ans1;
			last2 = ans4;
		}
	}
	else if (ans3 == 0)
	{
		last3 = ans2;
		if (g[x][y - 1] == 'A')
		{
			last1 = ans1;
			last2 = ans4;
		}
		else
		{
			last1 = ans4;
			last2 = ans1;
		}
	}
	else if (ans4 == 0)
	{
		last3 = ans1;
		if (g[x][y + 1] == 'A')
		{
			last1 = ans2;
			last2 = ans3;
		}
		else
		{
			last1 = ans3;
			last2 = ans2;
		}
	}

	cout << last1 << ' ' << last2 << ' ' << last3 << '\n';
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 488K, 提交时间: 2018-05-02 10:22:24

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
//--Container
#include<stack>
#include<vector>
#include<bitset>
//--
#define clr(a) memset(a,0,sizeof(a))
typedef long long ll;
char cz[110][110];bool bd[110][110];int mt[110][110],n,m,_A,_B,vc[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
inline bool _ck(int a,int b){return a>=0&&b>=0&&a<=n+1&&b<=m+1;};
void dfs(int a,int b,int d){
	int i,j;for(j=i=0;i<4;++i){int _a=a+vc[i][0],_b=b+vc[i][1];if(cz[_a][_b]&&cz[_a][_b]!='.')++j;}
	if(j==2)for(i=0;i<4;++i){int _a=a+vc[i][0],_b=b+vc[i][1];if(cz[_a][_b]=='X'&&!bd[_a][_b])bd[_a][_b]=1,dfs(_a,_b,i);};
	if(j==3)for(i=0;i<4;++i){int _a=a+vc[i][0],_b=b+vc[i][1];if(cz[_a][_b]=='X'&&!bd[_a][_b]&&((d&1)!=(i&1)))bd[_a][_b]=1,dfs(_a,_b,i);};
	if(j==4)for(i=0;i<4;++i){int _a=a+vc[i][0],_b=b+vc[i][1];if(cz[_a][_b]=='X'&&!bd[_a][_b]&&((d&1)==(i&1)))bd[_a][_b]=1,dfs(_a,_b,i);};
};
void dfx(int a,int b){
	int i,j;for(bd[a][b]=1,i=0;i<4;++i){int _a=a+vc[i][0],_b=b+vc[i][1];if(_ck(_a,_b)&&!bd[_a][_b])dfx(_a,_b);}
};
void dfz(int a,int b,int&rs){
	int i,j;if(cz[a][b]=='.'){mt[a][b]++;rs++;}for(bd[a][b]=1,i=0;i<4;++i){int _a=a+vc[i][0],_b=b+vc[i][1];if(!bd[_a][_b])dfz(_a,_b,rs);}
};
void cl(){
	int i,j,k,t,d;scanf("%d %d",&n,&m);for(clr(cz),clr(mt),i=1;i<=n;scanf("%s",cz[i++]+1));
	for(_A=_B=0,i=1;i<=n;++i)for(j=1;j<=m;++j){
		if(cz[i][j]=='A'){
			clr(bd);bd[i][j]=1;dfs(i,j,0);dfx(0,0);
			for(k=1;k<=n;++k)for(t=1;t<=m;++t)if(!bd[k][t])dfz(k,t,_A);
		}
		if(cz[i][j]=='B'){
			clr(bd);bd[i][j]=1;dfs(i,j,0);dfx(0,0);
			for(k=1;k<=n;++k)for(t=1;t<=m;++t)if(!bd[k][t])dfz(k,t,_B);
		}
	}
	for(d=0,i=1;i<=n;++i)for(j=1;j<=m;++j)if(mt[i][j]==2)++d;
	printf("%d %d %d\n",_A-d,_B-d,d);
};

int main(){
#ifndef ONLINE_JUDGE
	 freopen("in.txt","r",stdin);
	 freopen("out.txt","w",stdout);
#endif
	 cl();
	 return 0;
 };

详情