C++ 返り値の結果の違いについて

##質問内容
競技プログラミングの閉路検出の問題(yukicoder:No.13 )を解きました.
返り値のとり方を変えることで答えが違う結果になりました.
(違う結果というのは全ての結果を試した上で,impossible,possibleの出力が異なる結果が出てしまったということです)
間違えたテスト結果を元に色々な方法で確認したのですがあまり理解できませんでした.
どうして異なる結果(例:テストケース1)になるのかを教えていただきたいです.
正解では,グローバル変数のflagを変更し,結果を出力し,
不正解では,関数の返り値の値によって結果を判定しています.
おそらく,グローバル変数のflagを変更しないとbool dfs()の関数をreturnしても,rep(i,4)のループの中で最終的にfalseが返って来た時に異なる結果が出力されるのではないかと考えています.

また、このようなミスに気づくためにはこれからどう対応すれば良いのでしょうか?
ご回答よろしくお願いします.

##コード

正解になったコード

c
1#define ll long long
2#define ffor(i,a,b) for (int i=(a);i<(b);i++)
3#define rfor(i,a,b) for (int i=(b)-1;i>=(a);i--)
4#define rep(i,n) for (int i=0;i<(n);i++)
5#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
6#include<iostream>
7#include<iomanip>
8#include<algorithm>
9#include<cmath>
10#include<string>
11#include<stack>
12#include<queue>
13#include<vector>
14#include<map>
15#define SIZE 100001
16#define MOD 1000000007
17#define INF 100000000
18using namespace std;
19
20int w,h;
21int field[101][101];
22int used[101][101];
23bool d[101][101];
24int dx[4] = {1, 0, -1, 0};
25int dy[4] = {0, 1, 0, -1};
26bool flag = false;
27
28void bfs(int y, int x, int py, int px, int num){
29    d[y][x] = true; used[y][x] = 1;
30    rep(i, 4){
31        int nowy = y + dy[i], nowx = x + dx[i];
32        if(nowy < 0 || h <= nowy || nowx < 0 || w <= nowx) continue;
33        //戻るの禁止
34        if(nowy == py && nowx == px) continue;
35        //違う番号なら
36        if(field[nowy][nowx] != num) continue;
37        //もし一度訪れた場所に戻るならflagをtrueにして終了
38        if(used[nowy][nowx]){
39            flag = true;
40            return;
41        }
42		bfs(nowy, nowx, y, x, num);
43    }
44
45    return;
46}
47
48int main(){
49    cin.tie(0);
50    ios::sync_with_stdio(false);
51
52    cin >> w >> h;
53    rep(i,h)rep(j,w) cin >> field[i][j];
54
55    rep(i,h)rep(j,w){
56        if(d[i][j]) continue;
57        rep(a,101)rep(b,101) used[a][b] = 0;
58        bfs(i, j, -1, -1, field[i][j]);
59    }
60
61    cout << ((flag)? "possible":"impossible") << endl;
62    return 0;
63}

不正解

c
1#define ll long long
2#define ffor(i,a,b) for (int i=(a);i<(b);i++)
3#define rfor(i,a,b) for (int i=(b)-1;i>=(a);i--)
4#define rep(i,n) for (int i=0;i<(n);i++)
5#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
6#include<iostream>
7#include<iomanip>
8#include<algorithm>
9#include<cmath>
10#include<string>
11#include<stack>
12#include<queue>
13#include<vector>
14#include<map>
15#define SIZE 100001
16#define MOD 1000000007
17#define INF 100000000
18using namespace std;
19
20int w,h;
21int field[101][101];
22int used[101][101];
23bool d[101][101];
24int dx[4] = {1, 0, -1, 0};
25int dy[4] = {0, 1, 0, -1};
26bool flag = false;
27
28bool bfs(int y, int x, int py, int px, int num){
29	d[y][x] = true; used[y][x] = 1;
30	rep(i, 4){
31		int nowy = y + dy[i], nowx = x + dx[i];
32		if(nowy < 0 || h <= nowy || nowx < 0 || w <= nowx) continue;
33		//戻るの禁止
34		if(nowy == py && nowx == px) continue;
35		//違う番号なら
36		if(field[nowy][nowx] != num) continue;
37		//もし一度訪れた場所に戻るならflagをtrueにして終了
38		if(used[nowy][nowx]) return true;
39                bfs(nowy, nowx, y, x, num);
40
41	}
42
43	return false;
44}
45
46int main(){
47	cin.tie(0);
48	ios::sync_with_stdio(false);
49
50	cin >> w >> h;
51	rep(i,h)rep(j,w) cin >> field[i][j];
52
53	rep(i,h)rep(j,w){
54		if(d[i][j]) continue;
55		rep(a,101)rep(b,101) used[a][b] = 0;
56		if(bfs(i, j, -1, -1, field[i][j])){
57			cout << "possible" << endl;
58			return 0;
59		}
60	}
61	cout << "impossible" << endl;
62	//cout << ((flag)? "possible":"impossible") << endl;
63	return 0;
64}

LouiS0616

2017/06/14 01:33

flagの取り扱い以外にも一か所変更がある気がするんですが、どうしてですか？

waya

2017/06/14 01:35

出力部分のことでしょうか?trueが出たらすぐに出力して答えを出力することでプログラムの速度を上げようと思いこのように変えました.わかりづらくてすみません.

LouiS0616

2017/06/14 01:38

いえ、関数bfs内のループの最終行のことです。

waya

2017/06/14 01:40

その違いによってどうして結果が異なるかという質問です.申し訳ありません.不正解の方法ではflagを用いずに返り値のみの判定で結果を出力しようとしました.

waya

2017/06/14 01:42

わかりづらかったようなので編集しました.指摘ありがとうございます.

waya

2017/06/14 02:42

大変申し訳ありません、私自身がコピペを間違っていました.修正いたします.

行動規範の内容に同意します

回答3件

ベストアンサー

こんにちは。

どうして異なる結果になるのかを教えていただきたいです.

main()関数内で２重ループを回してます。
前者はその全てのループを回って、どれか１つでもtrueならpossibleを出力しています。
後者は最初にfalseを返した時点でimpossibleを出力して終了してます。

ところで、リンク先にある最初のデータで、それと異なる出力でした。
テストしてませんね。問題外ですよ。

このようなミスに気づくためにはこれからどう対応すれば良いのでしょうか?

動作確認することです。基本中の基本です。

投稿2017/06/14 02:06

編集2017/06/14 02:16

Chironian

総合スコア23272

waya

2017/06/14 02:20

ご回答ありがとうございます. 前者のコードでも後者の返り値の場所で終了するタイミングは同じなのでだと思ったのですが違うのでしょうか. こちらのテスト結果はもちろん全て試しました. その結果がうまく行かず,特に異なる結果が出ている場合は力不足ながらも色々とprintしてどうして結果が異なるのか特定しようと試みました. それでもわからなかった上で質問しました.気分を悪くしてしまいすみません.

Chironian

2017/06/14 02:43 編集

いえいえ、気分を害してはいないですよ。こちらこそ誤解させてすいません。 > こちらのテスト結果はもちろん全て試しました. つまり、「ミスの存在に気づく方法」ではなく、「バグの原因を見つける方法」を聞かれていたのですね。読解ミスです。すいません。 > 前者のコードでも後者の返り値の場所で終了するタイミングは同じなのでだと思ったのですが違うのでしょうか. あああ、ごめんなさい。終了するタイミングは異なりますが、trueで中断しているのでこれで良いはずですね。 if (used[nowy][nowx]) return true; の後でbfs(nowy, nowx, y, x, num);を呼び出していないようです。次の文を追加すれば良さそうです。（最初の１つでのみテストしました。） if (bfs(nowy, nowx, y, x, num)) return true; 今回の場合は、私は２つのソースをツールで比較して相違点を見つけてデバッグしました。性能改善等を行っている時なら効果的な方法と思います。普通にデバッグ中なら、途中途中の値を出力してみて、あるべき姿と比較することが多いですが、「あるべき姿」を手で求めたり、他のプログラムで求めたり等の作業が必要になるので、この手の大量の出力があるプログラムではなかなかたいへんです。どのポイントで比較すれば「あるべき姿」を簡単にだせるのか、検討しつつ進めると良いと思います。

waya

2017/06/14 02:50

文章が拙くて誤解をさせてしまいました. 詳しいご回答本当にありがとうございます. bfsの呼び出しが抜けていました.単純なことに気づかず情けないです. ２つのソースの比較が大事なことをとても痛感いたしました・・・。現在競技プログラミングの題材を練習によりよくコードをかけるよう練習をしているのでとても参考になります. 今後の勉強にも活かせるような回答ありがとうございました.

行動規範の内容に同意します

すでに引数によって期待している結果がわかっている場合であれば単体テストコードを書けばよいと思われます。
単体テストコードの対象をいじった場合、いじった箇所に不具合があって結果が変わるようなことがあったら単体テストで気づくことができます。

【参考URL】
https://msdn.microsoft.com/ja-jp/library/hh598953.aspx

投稿2017/06/14 01:14

s.t.

総合スコア2021

waya

2017/06/14 02:52

回答ありがとうございます. こちらのURLの記事を参考に読んでみます.

行動規範の内容に同意します

このようなミスに気づくためにはこれからどう対応すれば良いのでしょうか?

どうやってバグを見つけるかについては既に回答がついていますが、若干目線を変えて「バグを作りこまないようにするには」という観点での意見をコメントします。

以下を気にするプログラマーの方は多いと思います。

グローバル変数は必要なときしか使わない
フラグを使わない

若干意味合いが違う上記ふたつですが、目指すところは同じで「論理を明快にする(そうすればバグは少なくなるだろう)」ことに通じる話だと思います。論理が明快になる理由は関数の機能が単純明快になるからと言えると思います。

関数の中で何かをしてある条件によってフラグをON/OFFしつつ戻ってくる場合、その関数の機能を一言で言えないことが多いと思います。

(A) 経路を探索する。成功したらflagがONになっている

だと、この関数の機能は「全探索を行い、ある条件が満たせたらついでにフラグを立てる」ことなのか、「ある条件が満たせる探索路を見つける」のか曖昧になります。また「グローバルなフラグを立てる」ことは「そのフラグを見てだれかが何かを判断している」ことをフラグをアクセスできる範囲の関数に対して気にしなくてはならなくなりますね。グローバル変数だとプログラム全体を見ることになってしまいます。一方、

(B) ある条件を満たす経路を見つける。結果として見つかったかどうかを返す(副作用は一切ない)

なら、機能がより明快です。微妙な違いではありますがその違いはアプリケーションが大きくなり関数の数が増えていくほどに重要になっていきます。また機能が複雑になればなるほどこうした配慮は重要になると思います。

もし複数のフラグを更新するような複雑すぎる設計になりそうなとき、「この関数はどうも複雑すぎるのでもっと単純な機能にできるはずだ」と気づけるようになれば「よりバグを作りこみにくく、人が見ても分かり易い、何より自分が見ても分かり易い」論理になると思います。

本件の例ですとbfsは充分に明快な機能をもっているにもかかわらず、計算結果を戻り値でかえさずなぜflagのセットで表現しようとしているのだろうと多くの人が最初に感じると思います。バグがあるかどうかを気にする前にそう感じると思うのです・・・

投稿2017/06/14 03:23

KSwordOfHaste

総合スコア18394

waya

2017/06/14 03:32

ご回答ありがとうございます. なるほど、そのような思考でプログラムを設計していけばいいのですね. 競技プログラミングでは単純な問題を解くことが多く,グローバル変数を多用していつも解いてしまっています. 初心者すぎてバグができるのは当たり前だからエラーが出てもいいから実装して,そのあとに直していこうという発想をしておりました. 普段から競技プログラミングの他にソフトの開発も少ししているので,意識していこうと思います.ありがとうございます.

KSwordOfHaste

2017/06/14 03:48

場合によっては効率優先のためにあえて複雑な論理にするということもあるかも知れません。しかし一般的にはわかりやすさを優先させたほうがよいと思います。

行動規範の内容に同意します

あなたの回答