結果

問題 No.697 池の数はいくつか
ユーザー watarimaycry2
提出日時 2020-03-05 22:48:47
言語 JavaScript
(node v23.5.0)
結果
MLE  
実行時間 -
コード長 5,234 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 6,948 KB
実行使用メモリ 524,500 KB
最終ジャッジ日時 2024-11-25 16:00:34
合計ジャッジ時間 85,266 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 TLE * 10 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

var input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split("\n");
var obj = {
  "list" : input,
  "index" : 0,
  "max" : input.length,
  "next" : function(){
    if(!this.hasNext()){throw "NoSuchElementException:次に要素は無いよ";}
    var returnObj = this.list[this.index];
    this.index++;
    return returnObj;
  },
  "hasNext" : function(){return (this.index < this.max);}
}
function next(){return obj.next();}
function nextInt(){return myconv(next(),1);}
function nextStrArray(){return myconv(next(),2);}//半角スペース分割
function nextIntArray(){return myconv(next(),4);}//半角スペース + 数値化
function nextCharArray(){return myconv(next(),6);}//1文字分割
function hasNext(){return obj.hasNext();}
function myout(t){console.log(t);}//標準出力
function myerr(t){console.error(t);}//標準エラー出力
//[no]要素の扱い。数値型
//不明値、異常時:引数そのまま返す　1:数値へ変換
//2:半角SPで分割 4:半角SPで分割し、数値配列へ
//6:1文字で分割  7:1文字で分割し、数値配列へ
//8:半角SPで結合 9:改行で結合 0:文字なしで結合
function myconv(i,no){try{switch(no){case 1:return parseInt(i);case 2:return i.split(" ");case 4:return i.split(" ").map((a)=>Number(a));case 6:return i.split("");case 7:return i.split("").map((a)=>Number(a));case 8:return i.join(" ");case 9:return i.join("\n");case 0:return i.join("");default:return i;}}catch(e){return i;}}
var unionFind = {
  "list" : null,
  //全てのインデックスは「-X(親、絶対値はグループの大きさ)」「自分が属する親(≒根)」のいずれかを持つ。
  //最初はみんなグループの大きさ1の親
  "init" : function(n){
    this.list = new Array(n).fill(-1);
  },
  //同じ親を持つか
  "isSame" : function(mae, ato){
    return this.getRootIndex(mae) == this.getRootIndex(ato);
  },
  //自身の親インデックスをたどって根っこに着く
  //親にたどり終えたら子に帰っていくついでに、子たちに「共通の親を持っている」ことを知らせる
  "getRootIndex" : function(index){
    if(this.list[index] < 0){
       return index;
    }else{
       this.list[index] = this.getRootIndex(this.list[index]);
      return this.list[index];
    }
  },
  //異なる親同士のまとまりを一つにする（同じ親ならスルー）
  //小さいグループの親が大きいグループの親の直下に着く
  //グループの大きさも更新する
  "doUnion" : function(mae, ato){
    var maeRoot = this.getRootIndex(mae);
    var atoRoot = this.getRootIndex(ato);
    if(!this.isSame(maeRoot, atoRoot)){
       if(this.getSize(maeRoot) > this.getSize(atoRoot)){
          this.list[maeRoot] += this.list[atoRoot];
         this.list[atoRoot] = maeRoot;
       }else if(this.getSize(maeRoot) < this.getSize(atoRoot)){
          this.list[atoRoot] += this.list[maeRoot];
         this.list[maeRoot] = atoRoot;      
       }else{
         if(maeRoot < atoRoot){
            this.list[maeRoot] += this.list[atoRoot];
            this.list[atoRoot] = maeRoot;
         }else{
            this.list[atoRoot] += this.list[maeRoot];
            this.list[maeRoot] = atoRoot;      
         }
       }
    }
  },
  //「-X(親、絶対値はグループの大きさ)」
  //なので、インデックスを指定→親を知る→親の持つグループの大きさがわかる。
  //ただしマイナス値なので、-1を掛け算して返す。
  "getSize" : function(index){
    return -this.list[this.getRootIndex(index)];
  }
}
Main();
function Main(){
  var one = nextIntArray();
  var H = one[0];
  var W = one[1];
  var list = new Array(H);
  for(var i = 0; i < H; i++){
    list[i] = nextIntArray();
  }
  var count = 1;
  var queue = [];
  //まずはすべての水のエリアにナンバーを振っていく
  //振って行く過程で、はばたんのためにキューに突っ込んでいく。
  for(var i = 0; i < H; i++){
	for(var j = 0; j < W; j++){
      if(list[i][j] != 0){
         list[i][j] = count;
        count++;
        //このキューは0以外で隣接するところを、同じグループ化させるため、
        //少ない数値を優先配置する。キューをとったとき、その座標とキュー[2]を比べて
        //座標の方が小さいなら何もしない
        queue.push([i,j,list[i][j]]);
      }
    }
  }
  var dy = [-1,0,1,0];
  var dx = [0,-1,0,1];
  while(queue.length > 0){
    var tmp = queue.shift();
    var tmpy = tmp[0];
    var tmpx = tmp[1];
    var tmpc = tmp[2];
    if(list[tmpy][tmpx] <= tmpc){
       tmpc = list[tmpy][tmpx];
    }else{
       list[tmpy][tmpx] = tmpc;
    }
    for(var i = 0; i < dy.length; i++){
      var nexty = tmpy + dy[i];
      var nextx = tmpx + dx[i];
      if(nexty < H && nexty >= 0 && nextx < W && nextx >= 0){
         if(list[nexty][nextx] != 0 && list[nexty][nextx] > tmpc){
            queue.push([nexty,nextx,tmpc]);
         }
      }
    }
  }
  var set = new Set();
  for(var i = 0; i < H; i++){
	for(var j = 0; j < W; j++){
      set.add(list[i][j]);
    }
  }
  if(set.has(0)){
     set.delete(0);
  }
  myout(set.size);
}
0