競技プログラミング JOI 薄氷渡り WAの原因

Question

JOIの薄氷渡りという問題を正解することができません。
https://atcoder.jp/contests/joi2009yo/tasks/joi2009yo_d
このコードをどのように書き換えれば
正答を得ることができますか?

#include <bits/stdc++.h>

using namespace std;
using Node = vector<vector<int>>;
vector<int> dxs ={1,0,-1,0}; 
vector<int> dys ={0,1,0,-1}; 
  int n,m;
int ans = 0;
// 深さ優先探索
vector<bool> seen;
void dfs(int x,int y,int v,vector<vector<int>> &G) {
   G[x][y] = 0;
  v++; 
  
ans = max(v,ans); 

  for(int i = 0; i < 4; i++){ 
    int x2	= x + dxs[i]; 
    int y2 = y + dys[i]; 
    if((0 <= x2 && x2 < x) && (0 <= y2 && y2 < y)){ 
      if(G[x2][y2] == 1){
        dfs(x2,y2,v,G);
  }
    }
  }
G[x][y] = 1;
}

int main() {
    
    cin >> n >> m;

     vector<vector<int>> G(n,vector<int>(m));
   
 
  for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){ 
  cin >> G[i][j];

}
  }
  for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){ 
 if(G[i][j]==1){

  dfs(i,j,0,G);
}
}
  }
  cout << ans;
}
 

Comments

[episteme]

しつもんはなんですか

[Zuishin]

解説
https://www.ioi-jp.org/joi/2008/2009-yo-prob_and_sol/2009-yo-t4/review/2009-yo-t4-review.html

正答例
https://atcoder.jp/contests/joi2009yo/submissions?f.Task=joi2009yo_d&f.LanguageName=C%2B%2B&f.Status=AC&f.User=

[djrjd]

このコードで、正答できない原因を教えていただきたいです。
質問を書かず、すいませんでした。

[Zuishin]

解説と正答例を見てもわからないということですか？

[djrjd]

正答例を見てみると理解できるのですが、それを模写したこのコードではすべての入力に対して1が出力されてしまい、自分では原因が分からず質問をしました。
重ねてお詫び申し上げます。

Answer 1

//20行目
if((0 <= x2 && x2 < x) && (0 <= y2 && y2 < y)){

この条件だと、探索中のマスの左上のマスしか条件に入っていません。探索候補である上下左右のマスが除外されてしまっているため、探索が打ち切りになってしまい、1が出力されます。

マス(x2, y2)が広場からはみ出ていないかを確かめるif文ですから、x, yではなく、右端と下端を表すn, mで挟みます。

if((0 <= x2 && x2 < n) && (0 <= y2 && y2 < m)){

後は、出力の末尾に改行を入れればACできると思います。

cout << ans << endl;

Comments

[djrjd]

ありがとうございました。
無事解決することができました。