Submission #1695559


Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

using ll = long long;
using P = pair<int, int>;

const int INF = 1e9;
const int MOD = 1e9 + 7;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

char grid[510][510];
bool black[510][510]; // マスが黒かどうか
int cnt_h[510], cnt_w[510]; // 縦、横それぞれについて行、列ごとの黒のマスの数
int maxi_w, maxi_h; // maxi_wは、行ごとの黒のマスの数の最大値。maxi_hは、ある列が全て黒のマスである個数。

int main() {
  // 入力
  int N;
  cin >> N;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cin >> grid[i][j];
    }
  }

  // 部分点解法なので、制約外は考えない。
  if (N > 3) {
    cout << 0 << endl;

    return 0;
  }

  // 部分点解法は、Nが2 or 3しかない。
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (grid[i][j] == '.') continue;

      black[i][j] = true;
      cnt_h[j]++;
      cnt_w[i]++;
      maxi_h = max(maxi_h, cnt_h[j]);
      maxi_w = max(maxi_w, cnt_w[i]);
    }
  }

  int ans = -1;
  if (maxi_w > 0) {
    ans = N;
    // 行ごとに見ていく
    for (int i = 0; i < N; i++) {
      if (cnt_w[i] == N) {
        ans = 0;
        break;
      } else if (cnt_w[i] == N - 1) {
        if (N == 2) {
          if (black[i][i]) ans = 1;
        } else {
          int white;
          int tmp = 0;
          for (int j = 0; j < 3; j++) if (!black[i][j]) white = j;
          for (int j = 0; j < 3; j++) {
            if (i == j) continue;
            if (black[j][white]) tmp = 1;
          }
          ans = 2 - tmp;
        }
      }

      if (N == 3) {
        if (cnt_w[i] == 1) {
          if (black[i][i]) ans = min(ans, 2);
        }
      }
    }

    // 列ごとに見ていき、cnt_h[j]がN未満であれば、ansに1を足していく
    for (int j = 0; j < N; j++) {
      if (cnt_h[j] < N) ans++;
    }
  }

  // 解答
  cout << ans << endl;

  return 0;
}

Submission Info

Submission Time
Task B - Row to Column
User university
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2292 Byte
Status WA
Exec Time 15 ms
Memory 512 KB

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 0 / 300 0 / 1000
Status
AC × 5
AC × 19
WA × 1
AC × 20
WA × 23
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt
Subtask 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt, 2_16.txt, 2_17.txt, 2_18.txt, 2_19.txt, 2_20.txt, 2_21.txt, 2_22.txt
Case Name Status Exec Time Memory
0_00.txt AC 1 ms 256 KB
0_01.txt AC 1 ms 256 KB
0_02.txt AC 1 ms 256 KB
0_03.txt AC 1 ms 256 KB
0_04.txt AC 1 ms 256 KB
1_00.txt AC 1 ms 256 KB
1_01.txt AC 1 ms 256 KB
1_02.txt AC 1 ms 256 KB
1_03.txt AC 1 ms 256 KB
1_04.txt AC 1 ms 256 KB
1_05.txt AC 1 ms 256 KB
1_06.txt AC 1 ms 256 KB
1_07.txt AC 1 ms 256 KB
1_08.txt AC 1 ms 256 KB
1_09.txt WA 1 ms 256 KB
1_10.txt AC 1 ms 256 KB
1_11.txt AC 1 ms 256 KB
1_12.txt AC 1 ms 256 KB
1_13.txt AC 1 ms 256 KB
1_14.txt AC 1 ms 256 KB
2_00.txt WA 15 ms 512 KB
2_01.txt AC 15 ms 512 KB
2_02.txt WA 15 ms 512 KB
2_03.txt WA 15 ms 512 KB
2_04.txt WA 15 ms 512 KB
2_05.txt WA 15 ms 512 KB
2_06.txt WA 15 ms 512 KB
2_07.txt WA 11 ms 512 KB
2_08.txt WA 15 ms 512 KB
2_09.txt WA 14 ms 512 KB
2_10.txt WA 14 ms 512 KB
2_11.txt WA 14 ms 512 KB
2_12.txt WA 14 ms 512 KB
2_13.txt WA 12 ms 512 KB
2_14.txt WA 13 ms 512 KB
2_15.txt WA 12 ms 512 KB
2_16.txt WA 12 ms 512 KB
2_17.txt WA 12 ms 512 KB
2_18.txt WA 10 ms 384 KB
2_19.txt WA 14 ms 512 KB
2_20.txt WA 10 ms 384 KB
2_21.txt WA 9 ms 384 KB
2_22.txt WA 14 ms 512 KB