/*
JAI JAGANNATH!
*/
//@Author : zanj0
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
// #define LOCAL // ← enable locally via -DLOCAL; keep commented for OJ
#define ff first
#define ss second
#define pb push_back
#define MOD 1000000007
#define inf 1000000000000000000LL
#define ps(x, y) fixed << setprecision(y) << x
#define w(x) \
int x; \
cin >> x; \
while (x--)
#define endl "\n"
#define timetaken cerr << "Time : " << 1000 * (long double)clock() / (long double)CLOCKS_PER_SEC << "ms\n"
typedef long long int lli;
#ifdef LOCAL
#define dbg(x) cerr << "[DBG] " << #x << " = " << (x) << '\n'
template <class A, class B>
ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ',' << p.second << ')'; }
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
os << '[';
for (size_t i = 0; i < v.size(); ++i)
{
if (i)
os << ',';
os << v[i];
}
return os << ']';
}
template <class K, class V>
ostream &operator<<(ostream &os, const map<K, V> &mp)
{
os << '{';
bool first = true;
for (const auto &kv : mp)
{
if (!first)
os << ',';
first = false;
os << kv.first << ':' << kv.second;
}
return os << '}';
}
template <class K, class V>
ostream &operator<<(ostream &os, const unordered_map<K, V> &mp)
{
os << '{';
bool first = true;
for (const auto &kv : mp)
{
if (!first)
os << ',';
first = false;
os << kv.first << ':' << kv.second;
}
return os << '}';
}
#else
#define dbg(x) ((void)0)
#endif
void zanj0()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
}
/*
────────────────────────────────────────────────────────────────────────
Problem Statement:
Observations:
Need to reach P before fire consumes.
Claims:
────────────────────────────────────────────────────────────────────────
*/
const int N = 11;
char grid[N][N];
bool IsInside(int i, int j)
{
return i >= 0 && i < N && j >= 0 && j < N;
}
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<vector<int>> CalculateFireTime()
{
vector<vector<int>> ret(N, vector<int>(N, INT_MAX));
queue<pair<int, int>> q;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (grid[i][j] == 'F')
{
q.push({i, j});
ret[i][j] = 0;
}
}
}
while (!q.empty())
{
pair<int, int> curr = q.front();
q.pop();
int x = curr.ff;
int y = curr.ss;
for (int k = 0; k < 4; k++)
{
int nx = curr.ff + dir[k][0];
int ny = curr.ss + dir[k][1];
if (IsInside(nx, ny) && ret[nx][ny] == INT_MAX)
{
ret[nx][ny] = ret[x][y] + 1;
q.push({nx, ny});
}
}
}
return ret;
}
map<int, pair<int, int>> pos;
int GetBit(int mask, int idx)
{
return (mask >> idx) & 1;
}
int GetTime(int base_time, pair<int, int> src, vector<vector<int>>& fire_time){
queue<pair<int, int>> q;
q.push(src);
if(base_time >= fire_time[src.ff][src.ss]) return INT_MAX;
vector<vector<int>> ret(N, vector<int>(N, INT_MAX));
ret[src.ff][src.ss] = base_time;
while(!q.empty()){
pair<int, int> curr = q.front();
q.pop();
for(int k = 0; k < 4; k++){
int nx = curr.ff + dir[k][0];
int ny = curr.ss + dir[k][1];
if(!IsInside(nx, ny)) return ret[curr.ff][curr.ss] + 1;
if(IsInside(nx, ny) && ret[nx][ny] == INT_MAX){
int new_time = ret[curr.ff][curr.ss] + 1;
if(new_time >= fire_time[nx][ny]) continue;
ret[nx][ny] = new_time;
q.push({nx, ny});
}
}
}
return INT_MAX;
}
void Solve()
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> grid[i][j];
}
}
vector<vector<int>> fire_time = CalculateFireTime();
int curr = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (grid[i][j] == 'P')
{
pos[curr] = {i, j};
curr++;
}
}
}
vector<int> dp(1 << curr, INT_MAX);
dp[0] = 0;
for (int mask = 0; mask < (1 << curr); mask++)
{
if (dp[mask] == INT_MAX)
continue;
for (int j = 0; j < curr; j++)
{
if (GetBit(mask, j) == 1)
continue;
int rescue_time = GetTime(dp[mask], pos[j], fire_time);
if(rescue_time == INT_MAX) continue;
int n_mask = mask | (1 << j);
dp[n_mask] = min(dp[n_mask], rescue_time);
}
}
int ret = 0;
for (int i = 0; i < dp.size(); i++)
{
if (dp[i] == INT_MAX)
continue;
ret = max(ret, __builtin_popcount(i));
}
cout << ret << endl;
}
int32_t main()
{
zanj0();
Solve();
timetaken;
return 0;
}
/*
GOLDEN RULES
• Solutions are simple.
• Proofs are simple.
• Implementations are simple.
*/