結果

問題 No.348 カゴメカゴメ
コンテスト
ユーザー alpha_virginis
提出日時 2016-02-27 00:05:15
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,417 bytes
コンパイル時間 653 ms
コンパイル使用メモリ 71,908 KB
実行使用メモリ 18,120 KB
最終ジャッジ日時 2024-09-24 10:39:24
合計ジャッジ時間 7,371 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 52
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:43:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   43 |     scanf("%s", field[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#include <stack>

int N, M;
char field[1024][1024];

int bfs(int y, int x, char c1, char c2) {
  int res = 0;
  std::queue<int> xs;
  std::queue<int> ys;
  xs.push(x); ys.push(y);
  int dx[4] = {1, 0, -1, 0};
  int dy[4] = {0, 1, 0, -1};
  while( not xs.empty() ) {
    x = xs.front(); xs.pop();
    y = ys.front(); ys.pop();
    if( field[y][x] == c1 ) {
      field[y][x] = c2;
      res += 1;
    }
    else continue;
    for(int k = 0; k < 4; ++k) {
      int nx = x + dx[k];
      int ny = y + dy[k];
      if( not ( 0 <= nx and nx < M and 0 <= ny and ny < N ) ) continue;
      if( field[ny][nx] == c1 ) {
        xs.push(nx); ys.push(ny);
      }
    }
  }
  return res;
}
  
int main() {
  std::cin >> N >> M;
  for(int i = 0; i < N; ++i) {
    scanf("%s", field[i]);
  }

  int res = 0;
  int t1 = 0;
  for(int y : {0, N - 1}) {
    for(int x = 0; x < M; ++x) {
      t1 += bfs(y, x, '.', 'x');
    }
  }
  for(int y = 0; y < N; ++y) {
    for(int x : {0, M - 1}) {
      t1 += bfs(y, x, '.', 'x');
    }
  }

  int aa = bfs(0, 0, 'x', '.');
  res += aa - t1;

  for(;;) {
    bfs(0, 0, '.', 'x');
    bfs(0, 0, 'x', '.');
    int s = bfs(0, 0, '.', 'x');
    if( s == N * M ) break;
    int d = bfs(0, 0, 'x', '.');
    res += d - s;
  }

  printf("%d\n", res);
  
  return 0;
}
0