AtCoder Typical Contest 001 の A問題について

Question

実現したいこと

• ACが通るプログラムに修正する。
• WAになってしまう理由を理解する。

前提

AtCoderコンテスト ATC001 の A問題「深さ優先探索」の問題にチャレンジしています。
スタックを使用する等、他の解法もありますがこの質問では「なぜこのプログラムだとWAなのか」その理由を教えて欲しいです。

発生している問題・エラーメッセージ

唯一、テストケース「01_rnd_10.txt」だけWA判定になります。他のテストケースは全てAC判定です。

該当のソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int i = 0; i < (n); ++i)

char c[500][500];

void DFS(int x, int y, int limX, int limY, bool& ans){

	if(c[y][x]=='g') { // ゴールに来た
		ans = true;
		return;
	}else if(c[y][x]=='#' || x<0 || x>=limX || y<0 || y>=limY || c[y][x]=='*'){ // 壁or外or既出
		return;
	}

	c[y][x] = '*';

	DFS(x, y-1, limX, limY, ans);
	DFS(x+1, y, limX, limY, ans);
	DFS(x, y+1, limX, limY, ans);
	DFS(x-1, y, limX, limY, ans);
}

int main(){
	int h, w;
	cin >> h >> w;
	rep(i,h) rep(j,w) cin >> c[i][j];

	bool ans = false;

	rep(i,h) rep(j,w) {
 		if(c[i][j] == 's') DFS(j,i,w,h,ans);
	}

	cout << (ans ? "Yes" : "No") << endl; 
	return 0;
}

試したこと

ChatGPTやbingAIに質問しましたが、期待していた出力は得られませんでした。

Comments

[fana]

（この手のどこぞの問題の話を持ってくる人って，何故問題へのリンクを示さないのだろう？）

[Korudoputo]

ごめんなさい...！これがリンクです！
https://atcoder.jp/contests/atc001/tasks/dfs_a

[fana]

> 01_rnd_10.txt

とかいうやつの内容をどこから見れるのか探せなかったが，それはそれとして，
関数 DFS() の実装はこれだと範囲外参照しまくりなのでは？　と見える
（：(x,y) が範囲内にあるか否かの判定よりも先に c[y][x] にアクセスしてる）ので，
他の入力例で正解になる方が「たまたま」なのではなかろうか．

[fana]

あと，ゴールが見つかっても探索を打ち切らないのは効率悪そう．

[fana]

> 先に c[y][x] にアクセスしてる

念のために言っておくが
先頭のゴールの判定だけじゃなくて，その後の else if もだよ．
（後者側がピンとこない場合には　「短絡評価（ショートサーキット）」　とかでググると良いかと）

[Korudoputo]

範囲外判定をDFS()の最初に行うように変更したらACになりました...。
とても納得できました、ありがとうございます！
範囲外参照しっかり意識したいと思います...。

ちなみになのですが、この書き方の様な再帰関数の場合、ゴールが見つかった時点で他の探索を打ち切るというのは、DFS()の先頭に if(ans) return; を書いておけば良いという認識で良いでしょうか？

[fana]

> DFS()の先頭に if(ans) return; を書いておけば良い

とりあえずそれで良いと思います．

それはそれとして，
「ans を引数にとってそれを書き換える」という形にする必要が特段無いならば，結果を return で返す形の関数とするほうが素直(?)であるように思います．
で，DFS() 内末尾での4つの DFS() 呼び出しのところを

return ( DFS(x,y-1) || DFS(x+1,y) || DFS(x,y+1) || DFS(x-1,y) );

のように書くとか．（ここもまたショートサーキットになるので，いずれかがtrueを返してきた時点で後ろ側のDFS()呼び出しは成されない：探索の打ち切り）

[Korudoputo]

ありがとうございます。勉強になりました。

[fana]

問題が解決した場合には，この質問を何かしら適切な形で解決状態にしてください．
（ヘルプを見るに，「回答」が付いていない段階で問題が解決した場合には自己解決の形をとるのが良い様子です）

Answer 1

コメントで原因をご指摘いただき、修正することでACを通すことができました。大変勉強になりました。ありがとうございました。

WAの原因

DFS()内で、配列の範囲外参照チェックをする前に配列にアクセスしていたこと。

ACのソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int i = 0; i < (n); ++i)

char c[500][500];

bool DFS(int x, int y, int limX, int limY){

	if(x<0 || x>=limX || y<0 || y>=limY){ // 外
		return false;
	}else if(c[y][x]=='g') { // ゴールに来た
		return true;
	}else if(c[y][x]=='#' || c[y][x]=='*'){ // 壁or既出
		return false;
	}

	c[y][x] = '*';

	return (DFS(x, y-1, limX, limY) || DFS(x+1, y, limX, limY) || DFS(x, y+1, limX, limY) || DFS(x-1, y, limX, limY) );
}

int main(){
	int h, w;
	cin >> h >> w;
	rep(i,h) rep(j,w) cin >> c[i][j];

	bool ans = false;

	rep(i,h) rep(j,w) {
 		if(c[i][j] == 's') ans = DFS(j,i,w,h);
	}

	cout << (ans ? "Yes" : "No") << endl; 
	return 0;
}