/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 1ms 440.0 KiB
#3 Accepted 1ms 532.0 KiB
#4 Accepted 1ms 532.0 KiB
#5 Accepted 1ms 532.0 KiB
#6 Accepted 1ms 768.0 KiB
#7 Accepted 1ms 348.0 KiB
#8 Accepted 1ms 552.0 KiB
#9 Accepted 1ms 532.0 KiB
#10 Accepted 1ms 532.0 KiB
#11 Accepted 1ms 488.0 KiB
#12 Accepted 1ms 532.0 KiB
#13 Accepted 1ms 764.0 KiB
#14 Accepted 1ms 532.0 KiB
#15 Accepted 1ms 532.0 KiB
#16 Accepted 1ms 532.0 KiB
#17 Accepted 1ms 320.0 KiB
#18 Accepted 1ms 484.0 KiB
#19 Accepted 1ms 488.0 KiB
#20 Accepted 1ms 500.0 KiB
#21 Accepted 1ms 532.0 KiB
#22 Accepted 1ms 408.0 KiB
#23 Accepted 1ms 484.0 KiB
#24 Accepted 1ms 532.0 KiB
#25 Accepted 1ms 436.0 KiB
#26 Accepted 1ms 484.0 KiB
#27 Accepted 1ms 484.0 KiB
#28 Accepted 1ms 556.0 KiB
#29 Accepted 1ms 532.0 KiB
#30 Accepted 1ms 480.0 KiB
#31 Accepted 1ms 532.0 KiB
#32 Accepted 1ms 532.0 KiB
#33 Accepted 1ms 328.0 KiB
#34 Accepted 1ms 492.0 KiB
#35 Accepted 1ms 392.0 KiB
#36 Accepted 1ms 488.0 KiB
#37 Accepted 1ms 532.0 KiB
#38 Accepted 1ms 328.0 KiB
#39 Accepted 1ms 532.0 KiB
#40 Accepted 1ms 532.0 KiB
#41 Accepted 1ms 524.0 KiB
#42 Accepted 1ms 348.0 KiB
#43 Accepted 1ms 532.0 KiB
#44 Accepted 1ms 336.0 KiB
#45 Accepted 1ms 532.0 KiB
#46 Accepted 1ms 536.0 KiB
#47 Accepted 1ms 324.0 KiB
#48 Accepted 1ms 532.0 KiB
#49 Accepted 1ms 324.0 KiB
#50 Accepted 1ms 488.0 KiB
#51 Accepted 1ms 388.0 KiB
#52 Accepted 1ms 532.0 KiB
#53 Accepted 1ms 496.0 KiB
#54 Accepted 2ms 396.0 KiB
#55 Accepted 1ms 536.0 KiB
#56 Accepted 1ms 496.0 KiB
#57 Accepted 1ms 368.0 KiB
#58 Accepted 1ms 484.0 KiB
#59 Accepted 1ms 420.0 KiB
#60 Accepted 2ms 480.0 KiB
#61 Accepted 5ms 764.0 KiB
#62 Accepted 5ms 532.0 KiB
#63 Accepted 5ms 344.0 KiB
#64 Accepted 5ms 340.0 KiB
#65 Accepted 5ms 576.0 KiB
#66 Accepted 5ms 532.0 KiB
#67 Accepted 5ms 532.0 KiB
#68 Accepted 5ms 540.0 KiB
#69 Accepted 5ms 536.0 KiB
#70 Accepted 5ms 352.0 KiB
#71 Accepted 5ms 532.0 KiB
#72 Accepted 6ms 532.0 KiB
#73 Accepted 5ms 320.0 KiB
#74 Accepted 5ms 532.0 KiB
#75 Accepted 5ms 532.0 KiB
#76 Accepted 5ms 532.0 KiB
#77 Accepted 5ms 532.0 KiB
#78 Accepted 5ms 532.0 KiB
#79 Accepted 5ms 532.0 KiB
#80 Accepted 5ms 324.0 KiB
#81 Accepted 6ms 532.0 KiB
#82 Accepted 5ms 532.0 KiB
#83 Accepted 5ms 532.0 KiB
#84 Accepted 5ms 532.0 KiB
#85 Accepted 6ms 352.0 KiB
#86 Accepted 5ms 532.0 KiB
#87 Accepted 5ms 532.0 KiB
#88 Accepted 5ms 532.0 KiB
#89 Accepted 5ms 532.0 KiB
#90 Accepted 7ms 532.0 KiB
#91 Accepted 8ms 532.0 KiB
#92 Accepted 9ms 536.0 KiB
#93 Accepted 6ms 532.0 KiB
#94 Accepted 4ms 496.0 KiB
#95 Accepted 4ms 532.0 KiB
#96 Accepted 4ms 536.0 KiB
#97 Accepted 3ms 348.0 KiB
#98 Accepted 3ms 532.0 KiB
#99 Accepted 3ms 532.0 KiB
#100 Accepted 3ms 532.0 KiB

Code

/*
    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.
*/

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:08:41
Judged At
2026-01-06 16:08:41
Judged By
Score
100
Total Time
9ms
Peak Memory
768.0 KiB