Submission #880741

#	Time	Username	Problem	Language	Result	Execution time	Memory
880741		tsumondai	Dijamant (COCI22_dijamant)	C++14	70 / 70	277 ms	241236 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 2e3 + 5;

const int oo = 1e9, mod = 1e9 + 7;

int n, m, sol;
char c[N][N];
bool bio[N][N];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int mn_sum, mx_sum, mn_dif, mx_dif, ok, cnt;

void dfs (int x, int y) {
	if (x == 0 || x == n + 1 || y == 0 || y == m + 1) {
		ok = 0;
		return;
	}
	if (bio[x][y] || c[x][y] == '#') return;
	bio[x][y] = 1;
	cnt++;

	mn_sum = min(mn_sum, x + y);
	mx_sum = max(mx_sum, x + y);
	mn_dif = min(mn_dif, x - y);
	mx_dif = max(mx_dif, x - y);

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		dfs(nx, ny);
	}
}

void process() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> c[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (bio[i][j] || c[i][j] == '#') continue;

			mn_sum = mn_dif = 1e9;
			mx_sum = mx_dif = -1e9;
			ok = 1;
			cnt = 0;

			dfs(i, j);

			if (mx_sum - mn_sum == mx_dif - mn_dif && (mx_sum - mn_sum) % 2 == 0 && ok) {
				int d = (mx_sum - mn_sum) / 2 + 1;
				if (cnt == 2 * d * d - 2 * d + 1) sol++;
			}
		}
	}
	cout << sol;
	return;
}

signed main() {
	cin.tie(0)->sync_with_stdio(false);
	//freopen(".inp", "r", stdin);
	//freopen(".out", "w", stdout);
	process();
	cerr << "Time elapsed: " << __TIME << " s.\n";
	return 0;
}

/*
Xét các trường hợp đặc biệt
Kiểm tra lại input/output
Cố gắng trâu
Lật ngược bài toán
Keep calm and get VOI
Flow:

*/

• Subtask 1: 20 / 20
• Subtask 2: 50 / 50