Submission #420228


Source Code Expand

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>

#define INF_MIN 100000000
#define INF 1145141919
#define INF_MAX 2147483647
#define LL_MAX 9223372036854775807
#define EPS 1e-9
#define PI acos(-1)
#define LL long long

using namespace std;

#define MAX_H 500
#define MAX_W 500

int H, W;
char maze[MAX_H][MAX_W];
int sx, sy;

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

bool solve(int x, int y){
  
  if(maze[y][x] == 'g')
    return true;

  maze[y][x] = '#';

  for(int i = 0; i < 4; i++){
    int nx = x + dx[i];
    int ny = y + dy[i];
    if(0 <= nx && nx < W && 0 <= ny && ny < H && maze[ny][nx] != '#'){
      if(solve(nx, ny))
	return true;
    }
  }

  return false;

}

int main(){

  cin >> H >> W;
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> maze[i][j];
      if(maze[i][j] == 's'){
	sy = i;
	sx = j;
      }
    }
  }

  if(solve(sx, sy))
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

  return 0;

}

Submission Info

Submission Time
Task A - 深さ優先探索
User takoshi
Language C++ (GCC 4.9.2)
Score 100
Code Size 1436 Byte
Status AC
Exec Time 68 ms
Memory 4948 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 45 ms 868 KB
00_min_02.txt AC 26 ms 920 KB
00_min_03.txt AC 26 ms 928 KB
00_min_04.txt AC 27 ms 924 KB
00_min_05.txt AC 26 ms 928 KB
00_min_06.txt AC 28 ms 928 KB
00_min_07.txt AC 27 ms 920 KB
00_min_08.txt AC 25 ms 928 KB
00_sample_01.txt AC 26 ms 800 KB
00_sample_02.txt AC 28 ms 920 KB
00_sample_03.txt AC 27 ms 804 KB
00_sample_04.txt AC 27 ms 780 KB
00_sample_05.txt AC 27 ms 928 KB
01_rnd_00.txt AC 52 ms 980 KB
01_rnd_01.txt AC 55 ms 2260 KB
01_rnd_02.txt AC 56 ms 2076 KB
01_rnd_03.txt AC 61 ms 3788 KB
01_rnd_04.txt AC 62 ms 4816 KB
01_rnd_05.txt AC 51 ms 1052 KB
01_rnd_06.txt AC 55 ms 1616 KB
01_rnd_07.txt AC 53 ms 1356 KB
01_rnd_08.txt AC 52 ms 976 KB
01_rnd_09.txt AC 53 ms 984 KB
01_rnd_10.txt AC 56 ms 1232 KB
01_rnd_11.txt AC 52 ms 980 KB
01_rnd_12.txt AC 68 ms 4308 KB
01_rnd_13.txt AC 59 ms 3664 KB
01_rnd_14.txt AC 50 ms 976 KB
01_rnd_15.txt AC 56 ms 1888 KB
01_rnd_16.txt AC 53 ms 980 KB
01_rnd_17.txt AC 58 ms 1488 KB
01_rnd_18.txt AC 52 ms 972 KB
01_rnd_19.txt AC 62 ms 4948 KB
02_rndhard_00.txt AC 52 ms 980 KB
02_rndhard_01.txt AC 51 ms 1060 KB
02_rndhard_02.txt AC 52 ms 1060 KB
02_rndhard_03.txt AC 55 ms 1108 KB
02_rndhard_04.txt AC 52 ms 980 KB
02_rndhard_05.txt AC 52 ms 1000 KB
02_rndhard_06.txt AC 54 ms 1008 KB
02_rndhard_07.txt AC 51 ms 1060 KB
02_rndhard_08.txt AC 52 ms 1108 KB
02_rndhard_09.txt AC 53 ms 1052 KB
02_rndhard_10.txt AC 53 ms 1104 KB
02_rndhard_11.txt AC 52 ms 1100 KB
02_rndhard_12.txt AC 52 ms 1060 KB
02_rndhard_13.txt AC 53 ms 988 KB
02_rndhard_14.txt AC 52 ms 1100 KB
02_rndhard_15.txt AC 52 ms 1108 KB
02_rndhard_16.txt AC 51 ms 1072 KB
02_rndhard_17.txt AC 52 ms 980 KB
02_rndhard_18.txt AC 53 ms 976 KB
02_rndhard_19.txt AC 52 ms 980 KB
02_rndhard_20.txt AC 54 ms 1096 KB
02_rndhard_21.txt AC 52 ms 972 KB
02_rndhard_22.txt AC 54 ms 1180 KB
02_rndhard_23.txt AC 53 ms 1020 KB
02_rndhard_24.txt AC 54 ms 984 KB
02_rndhard_25.txt AC 51 ms 980 KB
02_rndhard_26.txt AC 52 ms 1064 KB
02_rndhard_27.txt AC 52 ms 1060 KB
02_rndhard_28.txt AC 51 ms 1064 KB
02_rndhard_29.txt AC 51 ms 980 KB
02_rndhard_30.txt AC 50 ms 976 KB
02_rndhard_31.txt AC 52 ms 976 KB
02_rndhard_32.txt AC 51 ms 976 KB
02_rndhard_33.txt AC 50 ms 976 KB
02_rndhard_34.txt AC 52 ms 980 KB
02_rndhard_35.txt AC 52 ms 992 KB
02_rndhard_36.txt AC 52 ms 976 KB
02_rndhard_37.txt AC 53 ms 976 KB
02_rndhard_38.txt AC 51 ms 1060 KB
02_rndhard_39.txt AC 51 ms 968 KB
03_rndhardsmall_00.txt AC 27 ms 928 KB
03_rndhardsmall_01.txt AC 29 ms 928 KB
03_rndhardsmall_02.txt AC 29 ms 928 KB
03_rndhardsmall_03.txt AC 25 ms 928 KB
03_rndhardsmall_04.txt AC 26 ms 924 KB
03_rndhardsmall_05.txt AC 27 ms 932 KB
03_rndhardsmall_06.txt AC 27 ms 924 KB
03_rndhardsmall_07.txt AC 26 ms 920 KB
03_rndhardsmall_08.txt AC 27 ms 924 KB
03_rndhardsmall_09.txt AC 31 ms 928 KB