ATC001 A - Depth First Search

Calendar Clock iconCalendar Clock icon

atcoder

Table of contents

# Problem

https://atcoder.jp/contests/atc001/tasks/dfs_a

# Input

HWH W
c0,0c0,1...c0,W1c_{0,0} c_{0,1} ... c_{0,W-1}
c1,0c1,1...c1,W1c_{1,0} c_{1,1} ... c_{1,W-1}
...
c_{H-1,0} c_{H-1,1} ... c_

  • HH - the length of height of rectangle
  • WW - the length of base of rectangle
  • ci,jc_{i, j} - Either of '.', '#', 's', 'g'

# Output

Weather you can get to g from s by going though only ..
You can go up, down, left or up (4 directions).

# Explanation

It can be solved with DFS starting from s.

# Time complexity

O(HW)O(H W)

# Solution

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;
#define MAX_N 501

Int H, W;
vector<bool> C(MAX_N*MAX_N, true);
Int sx, sy, gx, gy;

void dump(Int x, Int y, Int depth) {
  cout << "\033c";
  sleep_for(16ms);
  loop(h,0,H) {
    loop(w,0,W) {
      if (w == x && h == y) cout << "O";
      else cout << ".";
    }
    cout << endl;
  }
}

void input() {
  char x;
  cin >> H >> W;
  loop(h,0,H) {
    loop(w,0,W) {
      cin >> x;
      if (x == '#') C[h*W + w] = false;
      else if (x == 's') sx = w, sy = h;
      else if (x == 'g') gx = w, gy = h;
    }
  }
}

bool dfs(Int x, Int y, Int depth) {
  // dump(x, y, depth);
  if (gx == x && gy == y) return true;
  C[y*W+x] = false;
  loop(dy,-1,2) {
    loop(dx,-1,2) {
      if (dy != 0 && dx != 0) continue;
      Int x_ = x + dx, y_ = y + dy;
      if (x_ < 0 || W <= x_ || y_ < 0 || H <= y_) continue;
      if (!C[y_*W + x_]) continue;
      if (dfs(x_, y_, depth+1)) return true;
    }
  }
  return false;
}

void solve() {
  if (dfs(sx, sy, 0)) cout << "Yes" << endl;
  else cout << "No" << endl;
}

int main(void) {
  input();
  solve();
  return 0;
}

Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!

Comments