QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#560515 | #7733. Cool, It’s Yesterday Four Times More | PonyHex | TL | 0ms | 0kb | C++20 | 2.6kb | 2024-09-12 16:06:26 | 2024-09-12 16:06:26 |
answer
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define ll long long
#define double long double
#define lc u<<1
#define rc u<<1|1
#define X first
#define Y second
//#define int long long
const int N = 5e5 + 50;
const int M = 2005;
const ll maxm = 1e18 + 5;
const ll mod = 998244353;
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
struct node {
int sx, sy;
int x, y;
};
ll ans = 0;
char mp[5005][5005];
ll n, m;
bool vis[5005][5005];
bool vs[5005][5005];
bool bfs(int sx,int sy,int x,int y) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
vis[i][j] = 0;
}
}
queue<node>q;
q.push({ sx,sy,x,y });
while (q.size()) {
ll usx = q.front().sx;
ll usy = q.front().sy;
ll ux = q.front().x, uy = q.front().y;
q.pop(); vis[usx][usy] = 1; vs[usx][usy] = 1;
if (mp[ux][uy] == 'O')return true;
for (int i = 0; i < 4; i++) {
int vsx = usx + dx[i];
int vsy = usy + dy[i];
int vx = ux + dx[i], vy = uy + dy[i];
if (vsx >= 1 && vsx <= n && vsy >= 1 && vsy <= m) {
if (mp[vsx][vsy] == '.') {
if (vx >= 1 && vx <= n && vy >= 1 && vy <= m && mp[vx][vy] == '.') {
if (vis[vsx][vsy] == 0)
q.push({ vsx,vsy,vx,vy });
}
else
return true;
}
}
}
}
return false;
}
void solve()
{
ans = 0;
//其实暴力的写法就能过,赛时总是一开始就会去想思路,那些思路本身直接跳过了暴力思路
//榜并不可信,只是现在水平不够
//这题其实直接进行两两判定即可
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> mp[i][j];
}
}
vector<pair<ll, ll> >po;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (mp[i][j] == '.') {
po.push_back({ i,j });
}
}
}
int len = po.size();
for (int i = 0; i < len; i++) {
ll mid = 0;
for (int p = 1; p <= n; i++)
for (int q = 1; q <= m; q++)vs[p][q] = 0;
for (int j = 0; j < len; j++) {
if (i == j)continue;
if (vs[po[j].X][po[j].Y]) {
mid++; continue;
}
bool f=bfs(po[i].X, po[i].Y, po[j].X, po[j].Y);
if (f)mid++;
}
if (mid == len - 1)ans++;
}
cout << ans << endl;
return;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
std::cin >> T;
while (T--)
solve();
return 0;
}
ll ksm(ll a, ll b) {
ll base = a;
ll ans = 1;
while (b) {
if (b & 1)ans *= base;
base *= base;
b >>= 1;
}
return ans;
}
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
4 2 5 .OO.. O..O. 1 3 O.O 1 3 .O. 2 3 OOO OOO