Submission #28004301

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <algorithm>
#include <math.h>
#include <climits>
typedef long long LL;
using namespace std;

struct Route
{
    LL currentX = 0;
    LL currentY = 0;
    LL passedCount = 0;
};

int main()
{
    LL H = 0;
    cin >> H;
    LL W = 0;
    cin >> W;
    vector<string> C;
    for (LL i = 0LL; i < H; ++i)
    {
        string c;
        cin >> c;
        C.emplace_back(c);
    }

    LL maxCount = 0;
    deque<Route> candidates;
    Route initial;
    initial.passedCount = 1;
    candidates.push_back(initial);
    set<string> passedLog;
    while (candidates.size() > 0)
    {
        Route route = candidates.front();
        candidates.pop_front();

        string s;
        s.append(to_string(route.currentX));
        s.append("-");
        s.append(to_string(route.currentY));

        if (passedLog.find(s) == passedLog.end())
        {
            passedLog.insert(s);

            bool isFound = false;
            if (route.currentX < W - 1 && C[route.currentY][route.currentX + 1] == '.')
            {
                Route rightRoute;
                rightRoute.currentX = route.currentX + 1;
                rightRoute.currentY = route.currentY;
                rightRoute.passedCount = route.passedCount + 1;
                candidates.push_back(rightRoute);
                isFound = true;
            }
            if (route.currentY < H - 1 && C[route.currentY + 1][route.currentX] == '.')
            {
                Route belowRoute;
                belowRoute.currentX = route.currentX;
                belowRoute.currentY = route.currentY + 1;
                belowRoute.passedCount = route.passedCount + 1;
                candidates.push_back(belowRoute);
                isFound = true;
            }
            if (!isFound)
            {
                if (route.passedCount > maxCount)
                {
                    maxCount = route.passedCount;
                }
            }
        }
    }

    cout << maxCount << endl;
}

Submission Info

Submission Time
Task D - Weak Takahashi
User wfalps
Language C++ (GCC 9.2.1)
Score 400
Code Size 2162 Byte
Status AC
Exec Time 14 ms
Memory 4324 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 20
Set Name Test Cases
Sample example_00.txt, example_01.txt, example_02.txt
All example_00.txt, example_01.txt, example_02.txt, handmade.txt, test_00.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt
Case Name Status Exec Time Memory
example_00.txt AC 7 ms 3672 KiB
example_01.txt AC 3 ms 3620 KiB
example_02.txt AC 2 ms 3652 KiB
handmade.txt AC 14 ms 4172 KiB
test_00.txt AC 14 ms 4324 KiB
test_01.txt AC 12 ms 4008 KiB
test_02.txt AC 4 ms 3696 KiB
test_03.txt AC 2 ms 3628 KiB
test_04.txt AC 3 ms 3648 KiB
test_05.txt AC 2 ms 3660 KiB
test_06.txt AC 3 ms 3672 KiB
test_07.txt AC 2 ms 3668 KiB
test_08.txt AC 2 ms 3688 KiB
test_09.txt AC 2 ms 3572 KiB
test_10.txt AC 2 ms 3712 KiB
test_11.txt AC 3 ms 3672 KiB
test_12.txt AC 2 ms 3636 KiB
test_13.txt AC 3 ms 3664 KiB
test_14.txt AC 3 ms 3684 KiB
test_15.txt AC 2 ms 3588 KiB