QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#560515#7733. Cool, It’s Yesterday Four Times MorePonyHexTL 0ms0kbC++202.6kb2024-09-12 16:06:262024-09-12 16:06:26

Judging History

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

  • [2024-09-12 16:06:26]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [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

output:


result: