AtCoder Typical Contest 001

Submission #7143044

Source codeソースコード

#include <bits/stdc++.h>
#include <algorithm>
#include <math.h>
#include <queue>
#include <cstdio>
using namespace std;

template <class T> using V = vector<T>;
template <class S, class T> using P = pair<S, T>;
template <class... T> using TP = tuple<T...>;

using ll = long long;
using db = double;
using ldb = long db;
using str = string;
using vll = V<ll>;
using vvll = V<V<ll>>;
using vvvll = V<V<V<ll>>>;
using pll = P<ll,ll>;
using tpll = TP<ll,ll,ll>;
using vpll =V<pll>;
using vvpll = V<vpll>;
using vtpll = V<tpll>;
using vst = V<str>;
using vch = V<char>;
using vvch = V<vch>;

#define FOR(i,a,b) for(ll i=(a);i<(ll)(b);i++)
#define rFOR(i,a,b) for(ll i=(b);i>(ll)(a);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(ll)(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) __lcm(a,b)
#define co(a) cout<<a<<endl
#define ci(a) cin>>a
#define pb(a) push_back(a)
#define pob pop_back()
#define mp make_pair
#define mt make_tuple
#define pbmp(a,b) push_back(mp(a,b))
#define subs(a,b) substr(a,b)
#define cfs(a) cout<<fixed<<setprecision(a) //
#define INF 1e16
#define mod 1e9+7
/*vvll v(n,vll(m)) n行m列
A.erase(A.begin()+i); 配列Aのi番目を消せる
std::binary_search(v.bgn,v.en,a); 二分探索
abs(a,b)   pow(a,n)  to_string  stoll
auto Iter=lower_bound(v.bgn,v.en,a); v[i]>=aのv[i]
v.insert(lower_bound(v.bgn,v.en,a),b); bを入れられる
lower upper  co(*Iter) co(Iter-v.bgn) v[i]>=aのi
priority_queue<ll> pque;  pque.push(ai);
pque.top()=max(ai)  pque.pop() pque.sz
*/

const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
void Comuse() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
#define comuse Comuse()
ll combi(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

vvch v(500,vch(500));
vvll ve(500,vll(500));
bool D=false;
void dfs(ll sh,ll sw,ll h,ll w){
  if(D)return;
  if(ve[sh][sw]>0)return;
  ve[sh][sw]++;
  //co(sh<<sw);
  if(sh-1>=0){
    if(v[sh-1][sw]=='.')dfs(sh-1,sw,h,w);
    if(v[sh-1][sw]=='g')D=true;
  }
  if(sw-1>=0){
    if(v[sh][sw-1]=='.')dfs(sh,sw-1,h,w);
    if(v[sh][sw-1]=='g')D=true;
  }
  if(sh+1<h){
    if(v[sh+1][sw]=='.')dfs(sh+1,sw,h,w);
    if(v[sh+1][sw]=='g')D=true;
  }
  if(sw+1<w){
    if(v[sh][sw+1]=='.')dfs(sh,sw+1,h,w);
    if(v[sh][sw+1]=='g')D=true;
  }
}

int main(){
  ll h,w;
  cin>>h>>w;
  ll sh,sw;
  FOR(i,0,h){
    FOR(j,0,w){
      cin>>v[i][j];
      if(v[i][j]=='s'){
        sh=i,sw=j;
      }
    }
  }
  //co(v[0][0]);
  dfs(sh,sw,h,w);
  if(D)co("Yes");
  else co("No");
}

Submission

Task問題 A - 深さ優先探索
User nameユーザ名 Touri
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 3071 Byte
File nameファイル名
Exec time実行時間 26 ms
Memory usageメモリ使用量 11136 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_min_01.txt AC 2 ms 2432 KB
00_min_02.txt AC 2 ms 2432 KB
00_min_03.txt AC 2 ms 2432 KB
00_min_04.txt AC 2 ms 2432 KB
00_min_05.txt AC 3 ms 2432 KB
00_min_06.txt AC 2 ms 2432 KB
00_min_07.txt AC 2 ms 2432 KB
00_min_08.txt AC 2 ms 2432 KB
00_sample_01.txt AC 2 ms 2432 KB
00_sample_02.txt AC 2 ms 2432 KB
00_sample_03.txt AC 2 ms 2432 KB
00_sample_04.txt AC 2 ms 2432 KB
00_sample_05.txt AC 2 ms 2432 KB
01_rnd_00.txt AC 16 ms 2432 KB
01_rnd_01.txt AC 24 ms 9344 KB
01_rnd_02.txt AC 20 ms 4992 KB
01_rnd_03.txt AC 25 ms 10624 KB
01_rnd_04.txt AC 26 ms 11136 KB
01_rnd_05.txt AC 17 ms 2432 KB
01_rnd_06.txt AC 19 ms 4096 KB
01_rnd_07.txt AC 20 ms 5248 KB
01_rnd_08.txt AC 16 ms 2432 KB
01_rnd_09.txt AC 16 ms 2432 KB
01_rnd_10.txt AC 20 ms 2816 KB
01_rnd_11.txt AC 16 ms 2432 KB
01_rnd_12.txt AC 24 ms 9216 KB
01_rnd_13.txt AC 25 ms 8832 KB
01_rnd_14.txt AC 16 ms 2432 KB
01_rnd_15.txt AC 16 ms 2560 KB
01_rnd_16.txt AC 16 ms 2432 KB
01_rnd_17.txt AC 21 ms 3456 KB
01_rnd_18.txt AC 16 ms 2432 KB
01_rnd_19.txt AC 16 ms 2688 KB
02_rndhard_00.txt AC 16 ms 2432 KB
02_rndhard_01.txt AC 16 ms 2432 KB
02_rndhard_02.txt AC 17 ms 2560 KB
02_rndhard_03.txt AC 17 ms 2560 KB
02_rndhard_04.txt AC 16 ms 2432 KB
02_rndhard_05.txt AC 16 ms 2432 KB
02_rndhard_06.txt AC 16 ms 2432 KB
02_rndhard_07.txt AC 16 ms 2432 KB
02_rndhard_08.txt AC 16 ms 2560 KB
02_rndhard_09.txt AC 16 ms 2560 KB
02_rndhard_10.txt AC 16 ms 2560 KB
02_rndhard_11.txt AC 16 ms 2560 KB
02_rndhard_12.txt AC 16 ms 2560 KB
02_rndhard_13.txt AC 16 ms 2560 KB
02_rndhard_14.txt AC 16 ms 2560 KB
02_rndhard_15.txt AC 16 ms 2560 KB
02_rndhard_16.txt AC 16 ms 2432 KB
02_rndhard_17.txt AC 16 ms 2432 KB
02_rndhard_18.txt AC 16 ms 2432 KB
02_rndhard_19.txt AC 16 ms 2432 KB
02_rndhard_20.txt AC 16 ms 2560 KB
02_rndhard_21.txt AC 16 ms 2432 KB
02_rndhard_22.txt AC 17 ms 2560 KB
02_rndhard_23.txt AC 16 ms 2560 KB
02_rndhard_24.txt AC 16 ms 2432 KB
02_rndhard_25.txt AC 16 ms 2432 KB
02_rndhard_26.txt AC 16 ms 2432 KB
02_rndhard_27.txt AC 16 ms 2432 KB
02_rndhard_28.txt AC 16 ms 2432 KB
02_rndhard_29.txt AC 16 ms 2432 KB
02_rndhard_30.txt AC 16 ms 2432 KB
02_rndhard_31.txt AC 16 ms 2432 KB
02_rndhard_32.txt AC 16 ms 2560 KB
02_rndhard_33.txt AC 16 ms 2560 KB
02_rndhard_34.txt AC 16 ms 2432 KB
02_rndhard_35.txt AC 16 ms 2432 KB
02_rndhard_36.txt AC 16 ms 2432 KB
02_rndhard_37.txt AC 16 ms 2432 KB
02_rndhard_38.txt AC 16 ms 2432 KB
02_rndhard_39.txt AC 16 ms 2560 KB
03_rndhardsmall_00.txt AC 2 ms 2432 KB
03_rndhardsmall_01.txt AC 2 ms 2432 KB
03_rndhardsmall_02.txt AC 2 ms 2432 KB
03_rndhardsmall_03.txt AC 3 ms 2432 KB
03_rndhardsmall_04.txt AC 2 ms 2432 KB
03_rndhardsmall_05.txt AC 2 ms 2432 KB
03_rndhardsmall_06.txt AC 2 ms 2432 KB
03_rndhardsmall_07.txt AC 2 ms 2432 KB
03_rndhardsmall_08.txt AC 2 ms 2432 KB
03_rndhardsmall_09.txt AC 2 ms 2432 KB