Quiz

https://atcoder.jp/contests/joi2009yo/tasks/joi2009yo_d

AC code

https://atcoder.jp/contests/joi2009yo/submissions/10251707

解法

dfsで経路を全探索
dfs内でdfsをさらに呼ぶ時、呼ぶ前に状態を変更して、読んで戻ってきた後に状態を戻すテクがありますね。それを使いました

注意点

移動先の薄氷しか割れない
最初に孤立した薄氷からスタートした時は、飛び先がないので1枚も割れないので答えは0

code抜粋

ll ma;
ll F[100][100]; // fixed map
ll G[100][100];
ll W,H;

void reset_map(){
  rep(i, 100){
    rep(j, 100){
      G[i][j] = F[i][j];
    }
  }
}

int dx[4] = {-1, 0, 1,  0};
int dy[4] = { 0, 1, 0, -1};

bool in_range(ll i, ll j){
  if(0<=i && i<H && 0<=j && j<W){
    return true;
  }else{
    return false;
  }
}

void dfs(ll y, ll x, ll m){
  chmax(ma, m);
  rep(i, 4){
    ll ny = y + dy[i];
    ll nx = x + dx[i];
    if(in_range(ny, nx) && G[ny][nx]==1){
      G[ny][nx]=0;
      dfs(ny, nx, m+1);
      G[ny][nx]=1;      
    }
  }
}
    
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    cin>>W>>H;

    rep(i,H){
      rep(j,W){
        cin>>F[i][j];
      }
    }

    rep(i,H){
      rep(j,W){
        if(F[i][j]==1){
          reset_map();
          dfs(i, j, 0);
        }
      }
    }

    p(ma);

    return 0;
}