/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 768.0 KiB
#2 Accepted 2ms 540.0 KiB
#3 Accepted 2ms 540.0 KiB
#4 Accepted 2ms 328.0 KiB
#5 Accepted 3ms 332.0 KiB
#6 Accepted 5ms 540.0 KiB
#7 Time Exceeded ≥2099ms ≥5.027 MiB
#8 Time Exceeded ≥2001ms ≥5.035 MiB

Code

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

vector<pair<int, int>> dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
bool valid(int i, int j, int row_num, int col_num)
{
    if (i < 0 || i >= row_num)
    {
        return false;
    }

    if (j < 0 || j >= col_num)
    {
        return false;
    }

    return true;
}

// int floors(int si, int sj, int row_num, int col_num, vector<vector<char>> &grid, vector<vector<bool>> &vis)
// {
//     vis[si][sj] = true;
//     int area = 0;
//     for (auto mov : dirs)
//     {
//         int ci = si + mov.first;
//         int cj = sj + mov.second;

//         if (valid(ci, cj, row_num, col_num))
//         {
//             if (!vis[ci][cj] && grid[ci][cj] == '0')
//             {
//                 area += floors(ci, cj, row_num, col_num, grid, vis);
//             }
//         }
//     }

//     return area + 1;
// }

int floors(int si, int sj, int row_num, int col_num, vector<vector<char>> &grid, vector<vector<bool>> &vis)
{
    queue<pair<int, int>> q;
    q.push({si, sj});
    vis[si][sj] = true;
    int area = 1;

    while (!q.empty())
    {
        auto par = q.front();
        int par_i = par.first;
        int par_j = par.second;
        q.pop();

        for (auto mov : dirs)
        {
            int ci = par_i + mov.first;
            int cj = par_j + mov.second;

            if (valid(ci, cj, row_num, col_num))
            {
                if (!vis[ci][cj] && grid[ci][cj] == '0')
                {
                    q.push({ci, cj});
                    vis[ci][cj] = true;
                    area++;
                }
            }
        }
    }

    return area;
}

int main()
{
    int k;
    cin >> k;
    for (int f = 1; f <= k; f++)
    {
        int row_num, col_num;
        cin >> row_num >> col_num;
        vector<vector<char>> grid(row_num, vector<char>(col_num));
        vector<vector<bool>> vis(row_num, vector<bool>(col_num, false));

        for (int i = 0; i < row_num; i++)
        {
            for (int j = 0; j < col_num; j++)
            {
                cin >> grid[i][j];
            }
        }

        int max_area = INT_MIN;

        for (int i = 0; i < row_num; i++)
        {
            for (int j = 0; j < col_num; j++)
            {
                if (grid[i][j] == '0' && !vis[i][j])
                {
                    max_area = max(max_area, floors(i, j, row_num, col_num, grid, vis));
                }
            }
        }

        cout << "Floor #" << f << ": " << max_area << endl;
    }

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1002 Office Space
Language
C++17 (G++ 13.2.0)
Submit At
2025-02-16 14:21:03
Judged At
2025-02-16 14:21:03
Judged By
Score
60
Total Time
≥2099ms
Peak Memory
≥5.035 MiB