Submission #420562


Source Code Expand

#include <iostream>
#include <vector>

using namespace std;

int H, W;
vector<int> field;

int move[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

bool search(int x, int y, int goalX, int goalY)
{
    if (x == goalX && y == goalY)
        return true;

    int newX, newY;
    field[x + y * W] = 1;
    for (int i=0; i < 4; i++) {
        newX = x + move[i][0];
        newY = y + move[i][1];
        if (newX < 0 || W <= newX || newY < 0 || H <= newY)
            continue;
        if (field[newX + newY * W] == 1)
            continue;
        if (search(newX, newY, goalX, goalY))
            return true;
    }

    return false;
}

int main()
{
    int i;
    char input;
    int startX, startY, goalX, goalY;
    cin >> H >> W;
    for (i = 0; i < H*W; i++) {
        cin >> input;
        switch (input) {
        case 's':
            field.push_back(0);
            startX = i % W;
            startY = i / W;
            break;
        case 'g':
            field.push_back(0);
            goalX = i % W;
            goalY = i / W;
            break;
        case '.':
            field.push_back(0);
            break;
        default:
            field.push_back(1);
            break;
        }
    }

    if (search(startX, startY, goalX, goalY))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

Submission Info

Submission Time
Task A - 深さ優先探索
User notani
Language C++ (GCC 4.9.2)
Score 100
Code Size 1412 Byte
Status AC
Exec Time 81 ms
Memory 11804 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 5
AC × 83
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt
All 00_min_01.txt, 00_min_02.txt, 00_min_03.txt, 00_min_04.txt, 00_min_05.txt, 00_min_06.txt, 00_min_07.txt, 00_min_08.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 02_rndhard_00.txt, 02_rndhard_01.txt, 02_rndhard_02.txt, 02_rndhard_03.txt, 02_rndhard_04.txt, 02_rndhard_05.txt, 02_rndhard_06.txt, 02_rndhard_07.txt, 02_rndhard_08.txt, 02_rndhard_09.txt, 02_rndhard_10.txt, 02_rndhard_11.txt, 02_rndhard_12.txt, 02_rndhard_13.txt, 02_rndhard_14.txt, 02_rndhard_15.txt, 02_rndhard_16.txt, 02_rndhard_17.txt, 02_rndhard_18.txt, 02_rndhard_19.txt, 02_rndhard_20.txt, 02_rndhard_21.txt, 02_rndhard_22.txt, 02_rndhard_23.txt, 02_rndhard_24.txt, 02_rndhard_25.txt, 02_rndhard_26.txt, 02_rndhard_27.txt, 02_rndhard_28.txt, 02_rndhard_29.txt, 02_rndhard_30.txt, 02_rndhard_31.txt, 02_rndhard_32.txt, 02_rndhard_33.txt, 02_rndhard_34.txt, 02_rndhard_35.txt, 02_rndhard_36.txt, 02_rndhard_37.txt, 02_rndhard_38.txt, 02_rndhard_39.txt, 03_rndhardsmall_00.txt, 03_rndhardsmall_01.txt, 03_rndhardsmall_02.txt, 03_rndhardsmall_03.txt, 03_rndhardsmall_04.txt, 03_rndhardsmall_05.txt, 03_rndhardsmall_06.txt, 03_rndhardsmall_07.txt, 03_rndhardsmall_08.txt, 03_rndhardsmall_09.txt
Case Name Status Exec Time Memory
00_min_01.txt AC 28 ms 840 KB
00_min_02.txt AC 26 ms 800 KB
00_min_03.txt AC 28 ms 920 KB
00_min_04.txt AC 26 ms 800 KB
00_min_05.txt AC 26 ms 784 KB
00_min_06.txt AC 26 ms 924 KB
00_min_07.txt AC 26 ms 812 KB
00_min_08.txt AC 27 ms 796 KB
00_sample_01.txt AC 25 ms 924 KB
00_sample_02.txt AC 28 ms 796 KB
00_sample_03.txt AC 27 ms 676 KB
00_sample_04.txt AC 27 ms 924 KB
00_sample_05.txt AC 25 ms 800 KB
01_rnd_00.txt AC 54 ms 1948 KB
01_rnd_01.txt AC 65 ms 4888 KB
01_rnd_02.txt AC 63 ms 3356 KB
01_rnd_03.txt AC 66 ms 4764 KB
01_rnd_04.txt AC 63 ms 2840 KB
01_rnd_05.txt AC 60 ms 1936 KB
01_rnd_06.txt AC 61 ms 3232 KB
01_rnd_07.txt AC 68 ms 5660 KB
01_rnd_08.txt AC 54 ms 1948 KB
01_rnd_09.txt AC 59 ms 1936 KB
01_rnd_10.txt AC 61 ms 2324 KB
01_rnd_11.txt AC 55 ms 1948 KB
01_rnd_12.txt AC 57 ms 2968 KB
01_rnd_13.txt AC 55 ms 2452 KB
01_rnd_14.txt AC 55 ms 1944 KB
01_rnd_15.txt AC 60 ms 3088 KB
01_rnd_16.txt AC 53 ms 1952 KB
01_rnd_17.txt AC 64 ms 2816 KB
01_rnd_18.txt AC 55 ms 1948 KB
01_rnd_19.txt AC 81 ms 11804 KB
02_rndhard_00.txt AC 56 ms 1948 KB
02_rndhard_01.txt AC 54 ms 1940 KB
02_rndhard_02.txt AC 58 ms 1952 KB
02_rndhard_03.txt AC 57 ms 1944 KB
02_rndhard_04.txt AC 55 ms 1940 KB
02_rndhard_05.txt AC 56 ms 1948 KB
02_rndhard_06.txt AC 55 ms 1944 KB
02_rndhard_07.txt AC 59 ms 1948 KB
02_rndhard_08.txt AC 57 ms 1944 KB
02_rndhard_09.txt AC 60 ms 1936 KB
02_rndhard_10.txt AC 59 ms 1876 KB
02_rndhard_11.txt AC 58 ms 1940 KB
02_rndhard_12.txt AC 56 ms 1924 KB
02_rndhard_13.txt AC 58 ms 1940 KB
02_rndhard_14.txt AC 56 ms 1940 KB
02_rndhard_15.txt AC 55 ms 1996 KB
02_rndhard_16.txt AC 55 ms 1944 KB
02_rndhard_17.txt AC 56 ms 1940 KB
02_rndhard_18.txt AC 56 ms 1928 KB
02_rndhard_19.txt AC 56 ms 1956 KB
02_rndhard_20.txt AC 59 ms 1948 KB
02_rndhard_21.txt AC 56 ms 1956 KB
02_rndhard_22.txt AC 57 ms 1944 KB
02_rndhard_23.txt AC 57 ms 1944 KB
02_rndhard_24.txt AC 58 ms 1948 KB
02_rndhard_25.txt AC 56 ms 1948 KB
02_rndhard_26.txt AC 56 ms 1940 KB
02_rndhard_27.txt AC 55 ms 1944 KB
02_rndhard_28.txt AC 57 ms 1952 KB
02_rndhard_29.txt AC 56 ms 1936 KB
02_rndhard_30.txt AC 58 ms 1948 KB
02_rndhard_31.txt AC 57 ms 1988 KB
02_rndhard_32.txt AC 56 ms 1940 KB
02_rndhard_33.txt AC 56 ms 1944 KB
02_rndhard_34.txt AC 56 ms 1952 KB
02_rndhard_35.txt AC 57 ms 1952 KB
02_rndhard_36.txt AC 58 ms 1948 KB
02_rndhard_37.txt AC 56 ms 1948 KB
02_rndhard_38.txt AC 56 ms 1944 KB
02_rndhard_39.txt AC 59 ms 1944 KB
03_rndhardsmall_00.txt AC 25 ms 924 KB
03_rndhardsmall_01.txt AC 26 ms 800 KB
03_rndhardsmall_02.txt AC 25 ms 804 KB
03_rndhardsmall_03.txt AC 26 ms 920 KB
03_rndhardsmall_04.txt AC 24 ms 924 KB
03_rndhardsmall_05.txt AC 25 ms 792 KB
03_rndhardsmall_06.txt AC 26 ms 920 KB
03_rndhardsmall_07.txt AC 25 ms 792 KB
03_rndhardsmall_08.txt AC 25 ms 788 KB
03_rndhardsmall_09.txt AC 25 ms 796 KB