深さ優先探索の練習

昨日勉強した深さ優先探索の練習です。こういうのをパパっと5分くらいで書けるようになりたいです。
AtCoder Typical Contest のA問題

迷路のスタートからゴールまでたどり着けるか判定せよって問題ですね。同じ迷路でも、ゴールまでの最短経路を求める問題だと幅優先探索(Breadth First Search)ってのが使われるらしいです。

以下は自分のコードです。僕は一度訪れたマスを'#'で塗りつぶしていきましたが、解答例では迷路と同じ大きさの二次元配列(bool reached[H][W])を用意して各マスについて訪れたことがあるかどうか判定してました。

1. int dy[4] = { 0,0,1,-1 };
2. int dx[4] = { 1,-1,0,0 };
3.  
4. int H, W;
5. //迷路を表す配列
6. char meiro[501][501];
7.  
8. //位置(x,y)からゴールまでたどり着けるか判定する
9. bool dfs(int x, int y) {
10. //現在位置がゴールならOK
11. if (meiro[x][y] == 'g') {
12. return true;
13. }
14.  
15. //4方向について探索
16. REP(i, 4) {
17. //隣のマスの座標を(nx,ny)とする
18. int nx = x + dx[i];
19. int ny = y + dy[i];
20.  
21. //移動後のマスが迷路に収まっているか、あるいは通れないマスでないか判定
22. if (nx < 0 || nx >= H || ny < 0 || ny >= W || meiro[nx][ny] == '#')continue;
23. //さっきまでいたマスを'#'で塗りつぶす
24. meiro[x][y] = '#';
25. if (dfs(nx, ny))return true;
26. }
27. return false;
28. }
29.  
30. int main() {
31.  
32. cin >> H >> W;
33. int x=0, y=0;
34. REP(i, H) {
35. REP(j, W) {
36. cin >> meiro[i][j];
37. if (meiro[i][j] == 's') {
38. x = i; y = j;
39. }
40. }
41. }
42. if (dfs(x, y)) {
43. cout << "Yes" << endl;
44. return 0;
45. }
46. else {
47. cout << "No" << endl;
48. return 0;
49. }
50. }