QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#676720#7733. Cool, It’s Yesterday Four Times MoreYuanyin26RE 0ms3568kbC++203.5kb2024-10-25 23:31:012024-10-25 23:31:02

Judging History

你现在查看的是最新测评结果

  • [2024-10-25 23:31:02]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3568kb
  • [2024-10-25 23:31:01]
  • 提交

answer

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<string.h>
#include <string>
#include<math.h>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<map>
#include<queue>
#include<stack>
#include<functional>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define inf 1e18
const int N = 1e5+7;
const int M = 205;
const int mod = 1e9 + 7;
const int di[4][2] = { {1,0}, { -1,0 } ,{ 0,1 },{0,-1} };//下上右左
struct node
{
	int s;
	vector<int>x;
	vector<int>y;
	bool op = 0;
}; 
bool cmp(node a, node b)
{
	return a.s > b.s;
}
struct T
{
	int n, m;
	int cntqq;
	vector<vector<int>>a;
	vector<vector<bool>>vi;
	vector<node>tu;
	T()
	{
		cin >> n >> m;
		a.resize(n + 2, vector<int>(m + 2, -1));
		vi.resize(n + 2, vector<bool>(m + 2, 0));
		tu.resize(1);
		cntqq = 0;
		
	}
	inline void check(int x,int y,int p)
	{
		a[x][y] = p;
		if (tu.size() - 1 < p)
		{
			node tp;
			tp.x.push_back(x), tp.y.push_back(y);
			tp.s = 1;
			tu.push_back(tp);
		}
		else
		{
			tu[p].x.push_back(x), tu[p].y.push_back(y);
			tu[p].s++;
		}
		for (int i = 0; i < 4; i++)
			if (a[x + di[i][0]][y + di[i][1]] == 0)check(x + di[i][0], y + di[i][1], p);
		return;
	}
	/*
	inline bool dfs(int x1, int y1, int x2, int y2, int dx, int dy)
	{
		if (a[x1 + dx][y1 + dy] == -1)
		{
			return true;//没有包含关系
		}
		vi[x2 + dx][y2 + dy] = 1;
		for (int i = 0; i < 4; i++)
		{
			if (a[x2 + dx + di[i][0]][y2 + dy + di[i][1]] != -1 && vi[x2 + dx + di[i][0]][y2 + dy + di[i][1]] != 1)
				if (dfs(x1, y1, x2, y2, dx + di[i][0], dy + di[i][1]))
				{
					vi[x2 + dx][y2 + dy] = 0;
					return true;
				}
		}
		vi[x2 + dx][y2 + dy] = 0;
		return false;
	}*/
	
	inline int work(node A, node b)
	{
		int cnt = 0;
		for (int i = 0; i < A.x.size(); i++)
		{
			int x1 = A.x[i], y1 = A.y[i];
			int x2 = b.x[0], y2 = b.y[0];
			int cnt = 0;
			for (int j = 1; j < b.x.size(); j++)
			{
				int dx = b.x[j] - x2, dy = b.y[j] - y2;
				if (a[x1 + dx][y1 + dy] == -1)
				{
					cnt++;
				}
			}
			if (cnt == b.x.size() - 1)
			{
				if (A.s == b.s)return 2;//两个都不行
				else return 1;//小的不行
			}
		}
		return 0;//无所谓
	}
	/*
	inline int work(node A, node b)
	{
		for (int i = 0; i < A.x.size(); i++)
		{
			int x1 = A.x[i], y1 = A.y[i];

			int x2 = b.x[0], y2 = b.y[0];
			if (!dfs(x1, y1, x2, y2, 0, 0))
			{
				if (A.s == b.s)return 2;//两个都不行
				else return 1;//小的不行
			}
		}
		return 0;//无所谓
	}*/
	void so()
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
			{
				char tp;
				cin >> tp;
				if (tp == '.')
				{
					a[i][j] = 0;
				}
			}
		}//连通块
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
			{
				if (a[i][j] == 0)
				{
					check(i, j, ++cntqq);
				}

			}
		}//连通块
		sort(tu.begin() + 1, tu.end(), cmp);
		for (int i = 1; i <= cntqq; i++)
		{
			if (tu[i].op)continue;

			for (int j = i + 1; j <= cntqq; j++)
			{
				int oo = work(tu[i], tu[j]);
				if (oo == 1)tu[j].op = 1;
				else if (oo == 2)tu[i].op = tu[j].op = 1;
			}
		}
		int sum = 0;
		for (int i = 1; i <= cntqq; i++)
		{
			if (!tu[i].op)sum += tu[i].s;
		}
		cout << sum << endl;
	}
};
void solve()
{
	T x = T();
	x.so();
}

signed main()
{
	IOS;
	int T = 1;
	cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3568kb

input:

4
2 5
.OO..
O..O.
1 3
O.O
1 3
.O.
2 3
OOO
OOO

output:

3
1
0
0

result:

ok 4 lines

Test #2:

score: -100
Runtime Error

input:

200
2 4
OOO.
OO..
2 3
OOO
.O.
3 3
O.O
OOO
OO.
4 1
.
.
O
O
1 2
.O
1 1
.
2 5
.OO..
.O.O.
2 1
O
O
1 1
O
1 3
.OO
5 1
O
O
.
O
.
5 2
O.
..
O.
.O
..
5 3
...
...
.OO
..O
OOO
3 5
..O.O
.O.O.
.OO.O
5 2
.O
OO
O.
O.
..
2 1
O
O
3 5
.O.OO
O...O
..OO.
1 5
.....
5 1
O
.
O
.
.
5 3
OOO
OO.
.OO
OO.
O.O
2 1
O
.
5 2
O.
...

output:

3
0
0
2
1
1
3
0
0
1
0
4
9
4
4
0
6
5
2
0
1
6
4
5
2
0
0
5
3
3
1
4
1
0
4
5
2
3
7
3
0
6
2
2
2
0
4
6
6
3
3
2
3
3
2
1
0
3
3
4
4
2
2
0
7
6
4
8
5
3
2
5
2
1
2
1
4
0
0
2
5
1
4
6
6
1
6
2
2
3
4
5
2
1
0
1
9
3
4
11
0
3
2
1
0
0
4
3
1
4
3
8
3
0
3
0
2
3
1
3
3
4
0
2
11
2
2
4
0
4
0
0
2
1
2
3
0
5
0
16
4
3
2
6
0
8
3
3
1...

result: