Submission #9662770


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <numeric>
#include <unordered_map>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <memory>
#include <iomanip>
#include <type_traits>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
constexpr long long MOD = 1e9 + 7;
constexpr long long MAX = 1000000;

//long long MOD = 998244353;
constexpr ll INF = 1e17;
constexpr double PI = 3.141592653589793;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

ll h, w;
vector<ll> dx = { -1, 0, 1, 0 };
vector<ll> dy = { 0, -1, 0, 1 };


bool isInField(ll x, ll y) {
    bool f = x >= 0 && x < w && y >= 0 && y < h;
    return f;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int h, w;
    cin >> h >> w;
    vector<vector<char>> field(h, vector<char>(w));

    vector<int> dx = { 0,1,0,-1 };
    vector<int> dy = { 1,0,-1,0 };

    for (size_t rowIndex = 0; rowIndex < h; ++rowIndex)
    {
        for (size_t columnIndex = 0; columnIndex < w; ++columnIndex)
        {
            cin >> field[rowIndex][columnIndex];
        }
    }

    int max = -1;
    for (size_t rowIndex = 0; rowIndex < h; rowIndex++)
    {
        for (size_t columnIndex = 0; columnIndex < w; columnIndex++)
        {
            if (field[rowIndex][columnIndex] == '#') {
                continue;
            }
            vector<vector<int>> distance(h, vector<int>(w, -1));
            queue<pair<int, int>> q;
            q.push(make_pair(rowIndex, columnIndex));
            distance[rowIndex][columnIndex] = 0;
            while (!q.empty()) {
                auto current = q.front();
                q.pop();
                for (size_t i = 0; i < 4; ++i)
                {
                    int ny = current.first + dy[i];
                    int nx = current.second + dx[i];
                    if (nx < 0 || w <= nx || ny < 0 || h <= ny) {
                        continue;
                    }
                    if (field[ny][nx] == '#' || distance[ny][nx] != -1) {
                        continue;
                    }
                    distance[ny][nx] = distance[current.first][current.second] + 1;
                    q.push(make_pair(ny, nx));
                }
            }

            for (auto row : distance) {
                for (auto d : row) {
                    max = max < d ? d : max;
                }
            }
        }
    }

    cout << max << "\n";
    return 0;
}

Submission Info

Submission Time
Task D - Maze Master
User mmatthew_43
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2747 Byte
Status
Exec Time 5 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01, sample_02
All 400 / 400 hand_01, hand_02, hand_03, hand_04, hand_05, hand_06, hand_07, hand_08, hand_09, hand_10, sample_01, sample_02, small_01, small_02, small_03, small_04
Case Name Status Exec Time Memory
hand_01 2 ms 256 KB
hand_02 2 ms 256 KB
hand_03 1 ms 256 KB
hand_04 2 ms 256 KB
hand_05 4 ms 256 KB
hand_06 3 ms 256 KB
hand_07 2 ms 256 KB
hand_08 5 ms 256 KB
hand_09 1 ms 256 KB
hand_10 2 ms 256 KB
sample_01 1 ms 256 KB
sample_02 1 ms 256 KB
small_01 1 ms 256 KB
small_02 1 ms 256 KB
small_03 3 ms 256 KB
small_04 1 ms 256 KB