QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#676720 | #7733. Cool, It’s Yesterday Four Times More | Yuanyin26 | RE | 0ms | 3568kb | C++20 | 3.5kb | 2024-10-25 23:31:01 | 2024-10-25 23:31:02 |
Judging History
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...