結果

問題 No.866 レベルKの正方形
コンテスト
ユーザー nakaken88
提出日時 2019-08-17 09:34:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,093 bytes
コンパイル時間 1,781 ms
コンパイル使用メモリ 182,316 KB
実行使用メモリ 300,288 KB
最終ジャッジ日時 2024-09-24 18:57:55
合計ジャッジ時間 10,091 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 WA * 6 TLE * 1 -- * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int c(std::vector<long long int>)':
main.cpp:20:10: warning: 'temp' may be used uninitialized [-Wmaybe-uninitialized]
   20 |   return temp;
      |          ^~~~
main.cpp:16:7: note: 'temp' was declared here
   16 |   int temp;
      |       ^~~~
main.cpp: In function 'void check(int, int, int, int, std::vector<long long int>)':
main.cpp:25:8: warning: 'temp' may be used uninitialized [-Wmaybe-uninitialized]
   25 |   if (c(A) < K) return;
      |       ~^~~
main.cpp:16:7: note: 'temp' was declared here
   16 |   int temp;
      |       ^~~~
main.cpp:26:8: warning: 'temp' may be used uninitialized [-Wmaybe-uninitialized]
   26 |   if (c(A) == K) ans++;
      |       ~^~~
main.cpp:16:7: note: 'temp' was declared here
   16 |   int temp;
      |       ^~~~

ソースコード

diff # 

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

#define BR "\n"
#define SP " "
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << SP; } cout << BR;
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << BR;

ll H, W, K;
ll ans;
vector<vector<ll>> board(2000, vector<ll>(2000));
set <pair<pair<int, int>,int>> visited;

int c(vector<ll> x) {
  int temp;
  for (int i = 0; i < x.size(); i++) {
    if (x[i] > 0) temp++;
  }
  return temp;
}

void check(int sx, int sy, int ex, int ey, vector<ll> A) {
  visited.insert(make_pair(make_pair(sx, sy), ex - sx));
  if (c(A) < K) return;
  if (c(A) == K) ans++;
  if (sx == ex) return;

  vector<ll> A1 = A;
  for (int i = sx; i <= ex; i++) {
    A1[board[i][sy]]--;
  }
  vector<ll> A11 = A1;
  for (int i = sy + 1; i <= ey; i++) {
    A11[board[sx][i]]--;
  }
  if (visited.find(make_pair(make_pair(sx + 1, sy + 1), ex - sx - 1)) ==
      visited.end()) {
    check(sx + 1, sy + 1, ex, ey, A11);
  }

  vector<ll> A12 = A1;
  for (int i = sy + 1; i <= ey; i++) {
    A12[board[ex][i]]--;
  }
  if (visited.find(make_pair(make_pair(sx, sy + 1), ex - sx - 1)) ==
      visited.end()) {
    check(sx, sy + 1, ex - 1, ey, A12);
  }

  vector<ll> A2 = A;
  for (int i = sx; i <= ex; i++) {
    A2[board[i][ey]]--;
  }
  vector<ll> A21 = A2;
  for (int i = sy; i <= ey - 1; i++) {
    A21[board[sx][i]]--;
  }
  if (visited.find(make_pair(make_pair(sx + 1, sy), ex - sx - 1)) ==
      visited.end()) {
    check(sx + 1, sy, ex, ey - 1, A21);
  }

  vector<ll> A22 = A2;
  for (int i = sy; i <= ey - 1; i++) {
    A22[board[ex][i]]--;
  }
  if (visited.find(make_pair(make_pair(sx, sy), ex - sx - 1)) ==
      visited.end()) {
    check(sx, sy, ex - 1, ey - 1, A22);
  }
}

int main() {
  cin >> H >> W >> K;

  vector<ll> a(26, 0);

  for (int i = 0; i < H; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < s.size(); j++) {
      int alpha = s[j] - 'a';
      board[i][j] = alpha;
      a[alpha]++;
    }
  }
  ans = 0;
  check(0, 0, H - 1, W - 1, a);
  cout << ans << BR;

  return 0;
}
0