/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 7ms 532.0 KiB
#2 Accepted 4ms 532.0 KiB
#3 Accepted 9ms 532.0 KiB
#4 Accepted 4ms 324.0 KiB
#5 Accepted 4ms 560.0 KiB
#6 Accepted 5ms 532.0 KiB
#7 Accepted 5ms 532.0 KiB
#8 Accepted 13ms 548.0 KiB
#9 Accepted 20ms 556.0 KiB
#10 Accepted 5ms 324.0 KiB
#11 Accepted 9ms 532.0 KiB
#12 Accepted 5ms 532.0 KiB
#13 Accepted 5ms 532.0 KiB
#14 Accepted 7ms 564.0 KiB
#15 Accepted 5ms 532.0 KiB
#16 Accepted 4ms 560.0 KiB
#17 Accepted 4ms 532.0 KiB
#18 Accepted 14ms 532.0 KiB
#19 Accepted 6ms 556.0 KiB
#20 Accepted 4ms 532.0 KiB
#21 Accepted 4ms 532.0 KiB
#22 Accepted 8ms 532.0 KiB
#23 Accepted 7ms 320.0 KiB
#24 Accepted 6ms 532.0 KiB
#25 Accepted 16ms 536.0 KiB
#26 Accepted 13ms 560.0 KiB
#27 Accepted 12ms 564.0 KiB
#28 Accepted 16ms 536.0 KiB
#29 Accepted 17ms 532.0 KiB
#30 Accepted 13ms 552.0 KiB
#31 Accepted 12ms 480.0 KiB
#32 Accepted 11ms 532.0 KiB
#33 Accepted 12ms 480.0 KiB
#34 Accepted 14ms 488.0 KiB
#35 Accepted 12ms 532.0 KiB
#36 Accepted 30ms 556.0 KiB
#37 Accepted 24ms 532.0 KiB
#38 Accepted 6ms 532.0 KiB
#39 Accepted 16ms 552.0 KiB
#40 Accepted 11ms 468.0 KiB
#41 Accepted 13ms 532.0 KiB
#42 Accepted 15ms 488.0 KiB
#43 Accepted 11ms 532.0 KiB
#44 Accepted 14ms 324.0 KiB
#45 Accepted 13ms 480.0 KiB
#46 Accepted 13ms 552.0 KiB
#47 Accepted 28ms 564.0 KiB
#48 Accepted 5ms 324.0 KiB
#49 Accepted 5ms 532.0 KiB
#50 Accepted 6ms 568.0 KiB
#51 Accepted 16ms 532.0 KiB
#52 Accepted 11ms 568.0 KiB
#53 Accepted 6ms 488.0 KiB
#54 Accepted 34ms 552.0 KiB
#55 Accepted 4ms 564.0 KiB
#56 Accepted 18ms 564.0 KiB
#57 Accepted 38ms 552.0 KiB
#58 Accepted 5ms 532.0 KiB
#59 Accepted 11ms 440.0 KiB
#60 Accepted 368ms 556.0 KiB
#61 Accepted 4ms 768.0 KiB
#62 Accepted 3ms 532.0 KiB
#63 Accepted 4ms 460.0 KiB
#64 Accepted 6ms 484.0 KiB
#65 Accepted 14ms 536.0 KiB
#66 Accepted 4ms 324.0 KiB
#67 Accepted 5ms 532.0 KiB
#68 Accepted 31ms 556.0 KiB
#69 Accepted 6ms 320.0 KiB
#70 Accepted 7ms 552.0 KiB
#71 Accepted 8ms 556.0 KiB
#72 Accepted 65ms 560.0 KiB
#73 Accepted 6ms 564.0 KiB
#74 Accepted 5ms 532.0 KiB
#75 Accepted 16ms 556.0 KiB
#76 Accepted 16ms 552.0 KiB
#77 Accepted 10ms 532.0 KiB
#78 Accepted 9ms 360.0 KiB
#79 Accepted 12ms 532.0 KiB
#80 Accepted 9ms 556.0 KiB
#81 Accepted 122ms 556.0 KiB
#82 Accepted 8ms 560.0 KiB
#83 Accepted 23ms 560.0 KiB
#84 Accepted 7ms 320.0 KiB
#85 Accepted 73ms 556.0 KiB
#86 Accepted 11ms 764.0 KiB
#87 Accepted 86ms 560.0 KiB
#88 Accepted 25ms 532.0 KiB
#89 Accepted 13ms 512.0 KiB
#90 Accepted 372ms 560.0 KiB
#91 Accepted 1ms 532.0 KiB
#92 Accepted 1ms 536.0 KiB
#93 Accepted 33ms 556.0 KiB
#94 Accepted 123ms 556.0 KiB
#95 Accepted 256ms 556.0 KiB
#96 Accepted 6ms 532.0 KiB
#97 Accepted 6ms 556.0 KiB
#98 Accepted 10ms 560.0 KiB
#99 Accepted 5ms 532.0 KiB
#100 Accepted 18ms 560.0 KiB

Code

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int N = 1000005;
bool DEBUG = true;

int i, j, d, maxx, perm[9], tab[11][11], bat[11][11], dist[11][11], u, pre;
ii pers[9];
VI vv;
string s;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {-1, 1, 0, 0};

bool ok(int a, int b) {
	return a >=0 && a <= 10 && b >=0 && b <= 10;
}

void spread(int u) {
	queue<ii> q;
	for (int i=0;i<11;i++) for (int j=0;j<11;j++) if (bat[i][j]) {
		q.push(ii(i, j));
		dist[i][j] = 0;
	} else dist[i][j] = -1;
	while (!q.empty()) {
		ii w = q.front();
		q.pop();
		for (int k=0;k<4;k++) if (ok(w.first + dx[k], w.second + dy[k]) && dist[w.first + dx[k]][w.second + dy[k]] == -1) {
			q.push(ii(w.first + dx[k], w.second + dy[k]));
			dist[w.first + dx[k]][w.second + dy[k]] = dist[w.first][w.second] + 1;
		}
	}
	for (int i=0;i<11;i++) for (int j=0;j<11;j++) bat[i][j] = dist[i][j] <= u && dist[i][j] != -1;
}

bool canLeft(int x, int y) {
	int d = 0;
	while (x > 0) {
		x--;
		d++;
		for (int i=max(0, y - d);i<=min(10, y + d);i++) if (bat[x][i]) return false;
	}
	return true;
}

bool canRight(int x, int y) {
	int d = 0;
	while (x < 10) {
		x++;
		d++;
		for (int i=max(0, y - d);i<=min(10, y + d);i++) if (bat[x][i]) return false;
	}
	return true;
}

bool canUp(int x, int y) {
	int d = 0;
	while (y > 0) {
		y--;
		d++;
		for (int i=max(0, x - d);i<=min(10, x + d);i++) if (bat[i][y]) return false;
	}
	return true;
}

bool canDown(int x, int y) {
	int d = 0;
	while (y < 10) {
		y++;
		d++;
		for (int i=max(0, x - d);i<=min(10, x + d);i++) if (bat[i][y]) return false;
	}
	return true;
}

int tim(int ind) {
	int x = pers[ind].first;
	int y = pers[ind].second;
	if (bat[x][y]) return INF;
	int res = INF;
	if (x + 1 < res && canLeft(x, y)) res = x + 1;
	if (11 - x < res && canRight(x, y)) res = 11 - x;
	if (y + 1 < res && canUp(x, y)) res = y + 1;
	if (11 - y < res && canDown(x, y)) res = 11 - y;
	return res;
}

int get() {
	for (int i=0;i<11;i++) for (int j=0;j<11;j++) bat[i][j] = tab[i][j];
	for (int i=0;i<9;i++) {
		int u = tim(perm[i]);
		
		if (u == INF) return i;
		spread(u);
		/*if (DEBUG) {
			cout << u << endl;
			for (int j=0;j<11;j++) {
				for (int k=0;k<11;k++) cout << dist[j][k];
				cout << endl;
			}
		}*/
	}
	return 9;
}

bool same() {
	for (int i=0;i<vv.size();i++) if (perm[i] != vv[i]) return false;
	return true;
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

d = 0;
for (i=0;i<11;i++) for (j=0;j<11;j++) {
	cin >> s;
	if (s[0] == 'F') tab[i][j] = 1; else if (s[0] == 'P') pers[d++] = ii(i, j);
}
maxx = 0;
for (i=0;i<9;i++) perm[i] = i;
u = 0;
vv.pb(-1);
do {
	if (same()) continue;
	u = get();
	vv.clear();
	for (i=0;i<=min(8, u);i++) vv.pb(perm[i]);
	maxx = max(maxx, u);
} while (maxx < 9 && next_permutation(perm, perm + 9));
cout << maxx << endl;
return 0;
}

Information

Submit By
Type
Submission
Problem
P1221 G. Nine-eleven
Contest
Happy New Year 2026
Language
C++17 (G++ 13.2.0)
Submit At
2026-01-06 16:23:02
Judged At
2026-01-06 16:23:02
Judged By
Score
100
Total Time
372ms
Peak Memory
768.0 KiB