ふか杯 5th C-流れ

はじめに

2021年になりました。
私にとって2020年は競技プログラミング元年でした。
秋にAtCoder緑になりましたがここ３か月ほど停滞しています。

2021年はもっと力をつけて、まずは緑安定、できれば水色を目指して頑張りたいと思います。

ふか杯というのは京大マイコンクラブの部内向けコンテストだそうです。
マイコンクラブという名称が歴史の深さを感じさせます。

問題文

C - 流れ

高さの違うマスのグリッドのいくつかのマスに液体を注ぎます。
隣接マスが低い場合、液体が充たされます。
液体の広がるマスの個数を求めます。

考察

queueを使ったBFSで液体を注ぐマスを最初の入力とし、隣接マスが低い場合、隣接マスのチェックを入れて、隣接マスをキューに加えます。

最終的にチェックの入ったマスの数を数えます。

シンプルな問題ながらBFS書くのが久しぶりで20分くらいかかりました。

コード

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

typedef pair<int,int>P;
int w,h,p,x,y;
int Z[20][20];
int d[20][20];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

int main(){
  while(1){
    //入力
    cin>>w>>h>>p;
    if(w==0 && h==0 && p==0) break;
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        cin>>Z[j][i];
      }
    }
    //チェック初期化
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        d[j][i]=0;
      }
    }
    //キュー処理
    
    for(int i=0;i<p;i++){    
      cin>>x>>y;
      queue<P>que; 
      que.push(P(x,y));
      d[x][y]=1;
      while(que.size()){
        P p=que.front();
        que.pop();
        for(int j=0;j<4;j++){
          int nx=p.first+dx[j],ny=p.second+dy[j];
          if(0<=nx && nx<=w && 0<=ny && ny<=h && Z[nx][ny]<Z[p.first][p.second]){
            que.push(P(nx,ny));
            d[nx][ny]=1;
          }
        }
      }
      } 
      //カウントして結果出力
      int cnt=0;
      for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
          if(d[j][i]==1) cnt++;
        }
      }
    cout<<cnt<<endl;
  }
}

メモ

このコードの心臓部分のここですが

          if(0<=nx && nx<=w && 0<=ny && ny<=h && Z[nx][ny]<Z[p.first][p.second]){

nxが0を下回ったりwより大きかったりする場面もあり得ます。
Z[nx][ny]が範囲外参照にならないか心配しましたが大丈夫のようです。