寝癖頭の解法

学習中の覚え書きを投稿、更新していきます。

AtCoder Problems in C++ #E - イルミネーション (Illumination)

第11回日本情報オリンピック 予選(過去問)から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
競技プログラミング」を略して、「競プロ」などと呼ばれています。

#E - イルミネーション (Illumination)

atcoder.jp

僕が作成、提出したコードは、以下のとおりです。

/*
AtCoder Problems in C++
#E - イルミネーション (Illumination)
https://atcoder.jp/contests/joi2012yo/tasks/joi2012yo_e
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int v[102][102];
bool tf[102][102];
int w,h,ans=0;
void DFS(int s,int t){
  if(s>w+1 || t>h+1 || s<0 || t<0){
    return;
  }
  if(tf[s][t]){
    return;
  }
  if(v[s][t]==1){
    ans+=1;
    return;
  }
  tf[s][t]=true;
  if(t%2==0){
    DFS(s-1,t-1);
    DFS(s,t-1);
    DFS(s-1,t);
    DFS(s+1,t);
    DFS(s-1,t+1);
    DFS(s,t+1);
  }else{
    DFS(s,t-1);
    DFS(s+1,t-1);
    DFS(s-1,t);
    DFS(s+1,t);
    DFS(s,t+1);
    DFS(s+1,t+1);
  }
}
int main(void){
  cin>>w>>h;
  for(int j=1;j<=h;j++){
    for(int i=1;i<=w;i++){
      cin>>v[i][j];
    } 
  }
  DFS(0,0);
  cout<<ans<<endl;
  return 0;
}