パネルの大きさは答えに影響しないため、パネルを正方形(横方向に潰して)として考えてみましょう。以下の場合を考慮して、交わる箇所の個数を数えます。
- 縦方向の継ぎ目の線と電線は(x+1)回交わる
- 横方向の継ぎ目の線と電線は(y+1)回交わる
- ただし、壁の左上隅と右下隅で重複して数えているので、2を引く
- また、縦方向と横方向両方の継ぎ目の線(交点)と電線が交わる場合、重複して数えているので、それらの文を引く必要がある
- この重複の個数はxとyの最大公約数となる
以上の場合を考慮すると、答えとなる交点の個数は x + y - (gcd(x, y) -1) となります。ここでgcd(x, y)はxとyの最大公約数です。
参考文献:4つの言語で解ける 実践プログラミング問題集