Submission #4173955


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <climits>
#define bogo_sort   std::sort
#define bozo_sort   std::stable_sort
#define alles(obj)  obj.begin(), obj.end()
#define elif        else if
#define unless(flg) if(!(flg))
#define elless(flg) else if(!(flg))
#define echo        std::cout <<
#define read        std::cin >>
#define endl        std::endl
#define fin         << '\n'
#define bash        push_back
#define makePair    std::make_pair
#define _           << ' ' <<
// type-define
#define Stack       std::stack
#define Queue       std::queue
#define Set         std::set
#define PQueue      std::priority_queue
#define Vector      std::vector
#define Pair        std::pair
#define Map         std::map
#define UMap        std::unordered_map
#define Greater     std::greater
using String  =     std::string;
using llong   =     long long;
using boolean =     bool;
using Pii     =     Pair<int, int>;
using Vi      =     Vector<int>;
using Vii     =     Vector<Pii>;
// utils
constexpr int   dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int   dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
constexpr int   INF  = 0x3f3f3f3f;
constexpr llong LINF = 0x3f3f3f3f3f3f3f3fLL;

namespace {
    llong power ( llong x, llong n, llong mod ) {
        llong ans = 1;
        while ( n > 0 ) {
            if ( n & 1 ) ans = ( ans * x ) % mod;
            x = ( x * x ) % mod;
            n >>= 1;
        }
        return ans;
    }
    llong power ( llong x, llong n ) { return power( x, n, 1000000007 ); }
    llong gcd   ( llong x, llong y ) { return x % y ? gcd( y, x % y ) : y; }
    llong lcm   ( llong x, llong y ) { return ( x / gcd(x, y) * y ); }
    llong abs   ( llong n )          { return ( n < 0 ) ? -n : n; }
    template<class A, class B>inline bool chmax ( A &a, const B &b ) { return b > a ? a = b, true : false; }
    template<class A, class B>inline bool chmin ( A &a, const B &b ) { return b < a ? a = b, true : false; }
    boolean isMovable ( int x, int y, int w, int h ) {
        return ( x >= 0 && y >= 0 && x < w && y < h );
    }
}

namespace Rlyeh {

    char mas[512][512];

    signed call_of_Cthulhu( signed datum ) {

        int h, w;
        int sy, sx;
        read h >> w;
        for ( int i = 0; i < h; i++ ) {
            read mas[i];
            for ( int j = 0; j < w; j++ ) {
                if ( mas[i][j] == 's' ) {
                    sy = i;
                    sx = j;
                }
            }
        }
        Queue<Pii> q;
        q.push(Pii(sy, sx));
        while ( !q.empty() ) {
            Pii now = q.front();
            q.pop();
            int y = now.first;
            int x = now.second;
            for ( int i = 0; i < 4; i++ ) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if ( isMovable ( ny, nx, h, w ) && mas[ny][nx] != '#' ) {
                    if ( mas[ny][nx] == 'g' ) {
                        echo "Yes" fin;
                        return 0;
                    }
                    mas[ny][nx] = '#';
                    q.push(Pii(ny, nx));
                }
            }
        }
        echo "No" fin;

        return 0;
    }
}

signed main(){std::cin.tie(0); std::ios::sync_with_stdio(false); echo std::fixed << std::setprecision(8); int main_result = Rlyeh::call_of_Cthulhu(114514); return main_result;}

Submission Info

Submission Time
Task A - 深さ優先探索
User r1825
Language C++14 (GCC 5.4.1)
Score 100
Code Size 3734 Byte
Status
Exec Time 5 ms
Memory 512 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt
All 100 / 100 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 1 ms 256 KB
00_min_02.txt 1 ms 256 KB
00_min_03.txt 1 ms 256 KB
00_min_04.txt 1 ms 256 KB
00_min_05.txt 1 ms 256 KB
00_min_06.txt 1 ms 256 KB
00_min_07.txt 1 ms 256 KB
00_min_08.txt 1 ms 256 KB
00_sample_01.txt 1 ms 256 KB
00_sample_02.txt 1 ms 256 KB
00_sample_03.txt 1 ms 256 KB
00_sample_04.txt 1 ms 256 KB
00_sample_05.txt 1 ms 256 KB
01_rnd_00.txt 2 ms 512 KB
01_rnd_01.txt 2 ms 512 KB
01_rnd_02.txt 3 ms 512 KB
01_rnd_03.txt 4 ms 512 KB
01_rnd_04.txt 4 ms 512 KB
01_rnd_05.txt 2 ms 512 KB
01_rnd_06.txt 5 ms 512 KB
01_rnd_07.txt 4 ms 512 KB
01_rnd_08.txt 2 ms 512 KB
01_rnd_09.txt 2 ms 512 KB
01_rnd_10.txt 5 ms 512 KB
01_rnd_11.txt 2 ms 512 KB
01_rnd_12.txt 5 ms 512 KB
01_rnd_13.txt 2 ms 512 KB
01_rnd_14.txt 2 ms 512 KB
01_rnd_15.txt 4 ms 512 KB
01_rnd_16.txt 2 ms 512 KB
01_rnd_17.txt 5 ms 512 KB
01_rnd_18.txt 2 ms 512 KB
01_rnd_19.txt 3 ms 512 KB
02_rndhard_00.txt 2 ms 512 KB
02_rndhard_01.txt 2 ms 512 KB
02_rndhard_02.txt 2 ms 512 KB
02_rndhard_03.txt 2 ms 512 KB
02_rndhard_04.txt 2 ms 512 KB
02_rndhard_05.txt 2 ms 512 KB
02_rndhard_06.txt 2 ms 512 KB
02_rndhard_07.txt 2 ms 512 KB
02_rndhard_08.txt 2 ms 512 KB
02_rndhard_09.txt 2 ms 512 KB
02_rndhard_10.txt 2 ms 512 KB
02_rndhard_11.txt 2 ms 512 KB
02_rndhard_12.txt 2 ms 512 KB
02_rndhard_13.txt 2 ms 512 KB
02_rndhard_14.txt 2 ms 512 KB
02_rndhard_15.txt 2 ms 512 KB
02_rndhard_16.txt 2 ms 512 KB
02_rndhard_17.txt 2 ms 512 KB
02_rndhard_18.txt 2 ms 512 KB
02_rndhard_19.txt 2 ms 512 KB
02_rndhard_20.txt 2 ms 512 KB
02_rndhard_21.txt 2 ms 512 KB
02_rndhard_22.txt 2 ms 512 KB
02_rndhard_23.txt 2 ms 512 KB
02_rndhard_24.txt 2 ms 512 KB
02_rndhard_25.txt 2 ms 512 KB
02_rndhard_26.txt 2 ms 512 KB
02_rndhard_27.txt 2 ms 512 KB
02_rndhard_28.txt 2 ms 512 KB
02_rndhard_29.txt 2 ms 512 KB
02_rndhard_30.txt 2 ms 512 KB
02_rndhard_31.txt 2 ms 512 KB
02_rndhard_32.txt 2 ms 512 KB
02_rndhard_33.txt 2 ms 512 KB
02_rndhard_34.txt 2 ms 512 KB
02_rndhard_35.txt 2 ms 512 KB
02_rndhard_36.txt 2 ms 512 KB
02_rndhard_37.txt 2 ms 512 KB
02_rndhard_38.txt 2 ms 512 KB
02_rndhard_39.txt 2 ms 512 KB
03_rndhardsmall_00.txt 1 ms 256 KB
03_rndhardsmall_01.txt 1 ms 256 KB
03_rndhardsmall_02.txt 1 ms 256 KB
03_rndhardsmall_03.txt 1 ms 256 KB
03_rndhardsmall_04.txt 1 ms 256 KB
03_rndhardsmall_05.txt 1 ms 256 KB
03_rndhardsmall_06.txt 1 ms 256 KB
03_rndhardsmall_07.txt 1 ms 256 KB
03_rndhardsmall_08.txt 1 ms 256 KB
03_rndhardsmall_09.txt 1 ms 256 KB