読者です 読者をやめる 読者になる 読者になる

samayotta.show()

好きな映画は『たまこラブストーリー』です。

AOJ0071 Bomb Chain

投稿一発目はAOJのDFS。

爆弾の連鎖 | Aizu Online Judge

 

AOJ0071,Bomb Chain

 

 解説

メインロジックの再帰/DFSについては省略。

  • 四方向フィールド走査

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

for(int r = 0; r < 4; r++) {
  int nx = x + dx[r], ny = y + dy[r]; 
    if (MAP条件+問題条件) do something;

}

が"習いある手筋"。本問はこれの応用で正しい探索を実装できる。

cf)八方向フィールド走査のときは-1<=dx<=1,-1<=dy<=1で二重ループを回す。

  • フィールド座標

 この問題は全体の答案を書き上げるよりもこのバグフィックスに時間がかかった。わりに特殊な座標系の取り方に注意。0オリジンと1オリジンの帳尻合わせ他にも、さらに着火地点のマス目はfield[sy][sx]となる。