エイシングプログラミングコンテスト2019 C-Alternationg Path

エイシングプログラミングコンテスト2019　C-Alternationg Path

最初の検討

検討中です。
なかなかうまくいきません。
もう少し考えてみます。

#include <bits/stdc++.h>
using namespace std;

int H,W;
char E[410][410];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int dp[410][410];

long long dfs(int x,int y){
  if(dp[x][y] != -1) return dp[x][y];
  if(E[x][y]=='.') return 0;
  long long ret=1;
  for(int i=0;i<4;i++){
    int ny=y+dy[i];
    int nx=x+dx[i];
    if(nx< 0 || nx >=H || ny<0 || ny>=W) continue;
    if(E[x][y] == E[nx][ny]) continue;
    ret+=dfs(nx,ny);
  }
  return dp[x][y]=ret;
}
  

int main(){
  cin>>H>>W;
  string s;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      dp[i][j]=-1;
    }
  }
  
  //入力
  for(int i=0;i<H;i++){
    cin>>s;
    for(int j=0;j<W;j++){
      E[i][j]=s.at(j);
      //cout<<E[i][j];
    }
    //cout<<endl;
  }
    
  long long ans=0;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      ans+=dfs(i,j);
      //cout<<i<<" "<<j<<" "<<ans<<endl;
    }
  }
  cout<<ans<<endl;
  return 0;
}
 

解説読んで

解説読んでdfsの中身を工夫してみました。
サンプル通ってやったと思いましたが，WAが残るのでもう少し検討してみます。

#include <bits/stdc++.h>
using namespace std;

int H,W;
char E[410][410];
int checked[410][410];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int blk,wht;
char c; 

void dfs(int x,int y){
  
  checked[x][y]=1;
  if(E[x][y]=='#'){
    blk++;
    }
  else{
    wht++;
  }

  for(int i=0;i<4;i++){
    int ny=y+dy[i];
    int nx=x+dx[i];
    if(nx< 0 || nx >=H || ny<0 || ny>=W || checked[nx][ny]==1) continue;
    if(E[x][y] == E[nx][ny]) continue;
    dfs(nx,ny);
  }
}
 

int main(){
  cin>>H>>W;
  string s;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      checked[i][j]=0;
    }
  }
  
  //入力
  for(int i=0;i<H;i++){
    cin>>s;
    for(int j=0;j<W;j++){
      E[i][j]=s.at(j);
      //cout<<E[i][j];
    }
    //cout<<endl;
  }

  long long ans=0;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(checked[i][j]==0){
        blk=0;
        wht=0;
        dfs(i,j);
        ans+=blk*wht; 
      }
    }
  }

  cout<<ans<<endl;
  return 0;
}
 

AC!

３ケースだけ，しかも重たそうなケースをWAしているのでオーバーフローだなと気づきました。
禁断のdefin int long longで無事AC。

400*400程度でオーバーフローしたのに驚きましたが，たしかに400*400あれば黒8万白8万で積が64億になります。
int 型でオーバーフローするのは気づくべきでした。

考えたことなど

関数の扱いには少しは慣れてきたのですがまだまだ感覚がよくわかっていないところがあります。
今回のdfsでは引数でi,jを関数に渡してやっていますが，dfsでカウントした黒マスの数blkと白マスの数whtは特にあれこれ操作しなくてもメイン関数の方の変数に引き継がれています。

再帰は信じて投げてやるとわりとうまくいく，というのも最近身についた感覚です。