atcoder

# # Problem

## # Input

$H W$
$c_{0,0} c_{0,1} ... c_{0,W-1}$
$c_{1,0} c_{1,1} ... c_{1,W-1}$
...
c_{H-1,0} c_{H-1,1} ... c_

• $H$ - the length of height of rectangle
• $W$ - the length of base of rectangle
• $c_{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(H W)$

# # Solution

#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!