Submission #1176968
Source Code Expand
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <stdio.h>
#include <queue>
#include <stack>
#include <deque>
#include <math.h>
#include <sstream>
#include <stdlib.h>
#include <functional>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,a,n) for(int i = a; i < n; i++)
#define INF (1<<29)
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define fi first
#define se second
#define pb push_back
#define PI 3.14159265358979323846
#define all(o) (o).begin(), (o).end()
typedef double ld;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<ld> vd;
typedef vector < vc > vvc;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long int ulli;
const int dx[] = { 1, 0, -1, 0 };
const int dy[] = { 0, 1, 0, -1 };
template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
const ld eps = 1e-10, pi = acos(-1.0);
#define MAX_N 100001
// combination
ll fact[MAX_N], factinv[MAX_N];
ll mod_pow(ll n, ll p, ll m) {
ll a = n;
ll x = 1;
while (p) {
if (p & 1) x = (x * a) % m;
a = (a * a) % m;
p >>= 1;
}
return x;
}
int extgcd(int a, int b, int& x, int&y) {
int d = a;
if (b != 0) {
d = extgcd(b, a % b, y, x);
y -= (a / b) * x;
}
else {
x = 1; y = 0;
}
return d;
}
int mod_inverse(int a, int m) {
int x, y;
extgcd(a, m, x, y);
return (m + x % m) % m;
}
ll inv(ll n) {
return mod_pow(n, MOD - 2, MOD);
}
void combInit() {
fact[0] = 1;
rrep(i, 1, MAX_N) fact[i] = fact[i - 1] * i % MOD;
factinv[MAX_N - 1] = inv(fact[MAX_N - 1]);
for (int i = MAX_N - 2; i >= 0; i--) factinv[i] = factinv[i + 1] * (i + 1) % MOD;
}
// ダイクストラ
/*
struct edge { int to, cost; };
vector < vector < edge > > G;
vi d;
void dijkstra(int s) {priority_queue<pii, vector< pii >, greater<pii> > que;d[s] = 0;que.push(pii(0, s));while (!que.empty()) {pii p = que.top(); que.pop();int v = p.second;if (d[v] < p.first) continue;rep(i, G[v].size()) {edge e = G[v][i];int cost = e.cost;if (d[v] + cost < d[e.to]) {d[e.to] = d[v] + e.cost;que.push(pii(d[e.to], e.to));}}}}
*/
// Union-Find木
int par[MAX_N], rnk[MAX_N], unionSize[MAX_N];
// はじめは全ての頂点が根
void UnionFindTreeInit(int n) {
rep(i, n) {
par[i] = i;
rnk[i] = 0;
unionSize[i] = 1;
}
}
//木の根元を求める
int root(int x) {
if (par[x] == x) return x; // 根を返す
else return par[x] = root(par[x]);
}
// 連結成分の大きさを取得
int componentSize(int x) {
return unionSize[root(x)];
}
// xとyが同じ集合に属するか否か
bool same(int x, int y) {
return root(x) == root(y);
}
// xとyの属する集合を併合
void unite(int x, int y) {
x = root(x);
y = root(y);
if (x == y) return;
if (rnk[x] < rnk[y]) {
par[x] = y;
unionSize[y] += unionSize[x];
}
else {
par[y] = x;
if (rnk[x] == rnk[y]) rnk[x]++;
unionSize[x] += unionSize[y];
}
}
//-----------------------------------------------------------------
//int dx[8] = { -1, 1, 0, 0, 1, 1, -1, -1 };
//int dy[8] = { 0, 0, 1, -1, 1, -1, -1, 1 };
struct edge { int to, cost; };
vector < vector < edge > > G;
vi d;
void dijkstra(int s) {
priority_queue<pii, vector< pii >, greater<pii> > que;
d[s] = 0;
que.push(pii(0, s));
while (!que.empty()) {
pii p = que.top();
que.pop();
int v = p.second;
if (d[v] < p.first) continue;
rep(i, G[v].size()) {
edge e = G[v][i];
int cost = e.cost;
if (d[v] + cost < d[e.to]) {
d[e.to] = d[v] + e.cost;
que.push(pii(d[e.to], e.to));
}
}
}
}
char mp[600][600];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vvi a(n, vi(n));
rep(i, n) cin >> mp[i];
bool up = false, A = true;
rep(i, n) {
rep(j, n) {
if (mp[i][j] == '#') up = true;
else A = false;
}
}
if (!up) {
cout << -1 << endl;
return 0;
}
if (A) {
cout << 0 << endl;
return 0;
}
int ret = 600 * 600;
rep(i, n) {
int cnt = 0;
rep(j, n) {
if (mp[i][j] == '.') cnt++; // 白いマスをカウント
}
bool now = false;
rep(j, n) {
if (mp[j][i] == '#') now = true; // 黒いマスがj列に存在するか
}
if (!now) cnt++;//
ret = min(ret, cnt);
}
rep(i, n) {
rep(j, n) {
if (mp[j][i] == '.') {
ret++;
break;
}
}
}
cout << ret << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Row to Column |
User |
youki |
Language |
C++14 (GCC 5.4.1) |
Score |
1300 |
Code Size |
4714 Byte |
Status |
AC |
Exec Time |
3 ms |
Memory |
1536 KB |
Judge Result
Set Name |
Sample |
Subtask |
All |
Score / Max Score |
0 / 0 |
300 / 300 |
1000 / 1000 |
Status |
|
|
|
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 |
AC |
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 |
AC |
2 ms |
1536 KB |
2_01.txt |
AC |
2 ms |
1536 KB |
2_02.txt |
AC |
3 ms |
1536 KB |
2_03.txt |
AC |
3 ms |
1536 KB |
2_04.txt |
AC |
3 ms |
1536 KB |
2_05.txt |
AC |
3 ms |
1536 KB |
2_06.txt |
AC |
3 ms |
1536 KB |
2_07.txt |
AC |
2 ms |
1152 KB |
2_08.txt |
AC |
3 ms |
1536 KB |
2_09.txt |
AC |
3 ms |
1536 KB |
2_10.txt |
AC |
3 ms |
1536 KB |
2_11.txt |
AC |
3 ms |
1536 KB |
2_12.txt |
AC |
3 ms |
1536 KB |
2_13.txt |
AC |
2 ms |
1408 KB |
2_14.txt |
AC |
2 ms |
1408 KB |
2_15.txt |
AC |
2 ms |
1408 KB |
2_16.txt |
AC |
2 ms |
1408 KB |
2_17.txt |
AC |
2 ms |
1280 KB |
2_18.txt |
AC |
2 ms |
1152 KB |
2_19.txt |
AC |
3 ms |
1536 KB |
2_20.txt |
AC |
2 ms |
1152 KB |
2_21.txt |
AC |
2 ms |
1152 KB |
2_22.txt |
AC |
3 ms |
1536 KB |