// Author: @Drydock
use std::io::{self, Read};
const INF: i32 = 1000000000;
fn main() {
solve();
}
fn solve() {
let mut b = Vec::new();
io::stdin().read_to_end(&mut b).unwrap();
let mut g = [b'#'; 121];
let mut k = 0usize;
for &c in &b {
if c == b'#' || c == b'F' || c == b'P' {
if k < 121 {
g[k] = c;
k += 1;
}
}
}
if k < 121 {
return;
}
let mut ft = vec![INF; 121];
let mut q = [0usize; 121];
let mut h = 0usize;
let mut t = 0usize;
for i in 0..121 {
if g[i] == b'F' {
ft[i] = 0;
q[t] = i;
t += 1;
}
}
while h < t {
let u = q[h];
h += 1;
let du = ft[u] + 1;
let x = u / 11;
let y = u % 11;
if x > 0 {
let v = u - 11;
if ft[v] > du {
ft[v] = du;
q[t] = v;
t += 1;
}
}
if x + 1 < 11 {
let v = u + 11;
if ft[v] > du {
ft[v] = du;
q[t] = v;
t += 1;
}
}
if y > 0 {
let v = u - 1;
if ft[v] > du {
ft[v] = du;
q[t] = v;
t += 1;
}
}
if y + 1 < 11 {
let v = u + 1;
if ft[v] > du {
ft[v] = du;
q[t] = v;
t += 1;
}
}
}
let mut p = Vec::new();
for i in 0..121 {
if g[i] == b'P' {
p.push(i);
}
}
let n = p.len();
if n == 0 {
print!("0\n");
return;
}
let tm = 512usize;
let mut mc = vec![vec![i32::MIN; tm + 1]; n];
let msz = 1usize << n;
let mut dp = vec![INF; msz];
dp[0] = 0;
for m in 0..msz {
let ct = dp[m];
if ct >= INF {
continue;
}
let ctu = ct as usize;
if ctu > tm {
continue;
}
for i in 0..n {
if (m >> i) & 1 == 0 {
let mut e = mc[i][ctu];
if e == i32::MIN {
e = esc(p[i], ct, &ft);
mc[i][ctu] = e;
}
if e < INF {
let nm = m | (1usize << i);
if dp[nm] > e {
dp[nm] = e;
}
}
}
}
}
let mut an = 0u32;
for m in 0..msz {
if dp[m] < INF {
let c = (m as u32).count_ones();
if c > an {
an = c;
}
}
}
print!("{}\n", an);
}
fn esc(s: usize, t0: i32, ft: &[i32]) -> i32 {
if ft[s] <= t0 {
return INF;
}
let mut d = [-1i16; 121];
let mut q = [0usize; 121];
let mut h = 0usize;
let mut t = 0usize;
d[s] = 0;
q[t] = s;
t += 1;
while h < t {
let u = q[h];
h += 1;
let du = d[u] as i32;
let x = u / 11;
let y = u % 11;
if x == 0 || x == 10 || y == 0 || y == 10 {
return t0 + du + 1;
}
let nd = du + 1;
let at = t0 + nd;
if x > 0 {
let v = u - 11;
if d[v] < 0 && ft[v] > at {
d[v] = nd as i16;
q[t] = v;
t += 1;
}
}
if x + 1 < 11 {
let v = u + 11;
if d[v] < 0 && ft[v] > at {
d[v] = nd as i16;
q[t] = v;
t += 1;
}
}
if y > 0 {
let v = u - 1;
if d[v] < 0 && ft[v] > at {
d[v] = nd as i16;
q[t] = v;
t += 1;
}
}
if y + 1 < 11 {
let v = u + 1;
if d[v] < 0 && ft[v] > at {
d[v] = nd as i16;
q[t] = v;
t += 1;
}
}
}
INF
}
Drydock (Drydock) LV 8
judge
