Submission #1132377


Source Code Expand

#include <bits/stdc++.h>
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

template<class T> inline
void read(T& x) {
	int f = 1; x = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9')   {if (ch == '-') f = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
	x *= f;
}

/*============ Header Template ============*/

const int N = 500 + 5;

int n;
int a[N][N];
int c[N], d[N], inq[N];
char s[N][N];

queue<int> Q;

void SPFA() {
	for (int i = 1; i <= n; i++)
		if (d[i] == 0) {
			Q.push(i);
			inq[i] = 1;
		}
	while (!Q.empty()) {
		int x = Q.front(); Q.pop(); inq[x] = 0;
		for (int i = 1; i <= n; i++)
			if (d[i] > d[x] + 1) {
				d[i] = d[x] + 1;
				if (!inq[i]) {
					Q.push(i);
					inq[i] = 1;
				}
			}
	}
}

int main() {
	read(n);
	for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
	int mx = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			a[i][j] = (s[i][j] == '#');
			c[i] += a[i][j];
			mx = max(mx, c[i]);
		}
	if (mx == 0) {printf("-1\n"); return 0;}
	for (int i = 1; i <= n; i++) d[i] = INF;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) if (a[i][j]) d[j] = 0;
	SPFA();
	int tmp = INF, id = 0;
	for (int i = 1; i <= n; i++) {
		if (d[i] != INF && n - c[i] < tmp) {
			tmp = min(tmp, n - c[i] + d[i]);
			id = i;
		}
	}
	for (int j = 1; j <= n; j++) {
		for (int i = 1; i <= n; i++) {
			if (!a[i][j]) {
				tmp++;
				break;
			}
		}
	}
	printf("%d\n", tmp);
	return 0;
}

Submission Info

Submission Time
Task B - Row to Column
User cicada
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 1569 Byte
Status AC
Exec Time 4 ms
Memory 1536 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:47:52: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
                                                    ^

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 300 / 300 1000 / 1000
Status
AC × 5
AC × 20
AC × 43
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 3 ms 1536 KB
2_01.txt AC 3 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 3 ms 1280 KB
2_08.txt AC 4 ms 1536 KB
2_09.txt AC 3 ms 1408 KB
2_10.txt AC 3 ms 1408 KB
2_11.txt AC 4 ms 1536 KB
2_12.txt AC 4 ms 1408 KB
2_13.txt AC 4 ms 1408 KB
2_14.txt AC 4 ms 1408 KB
2_15.txt AC 3 ms 1408 KB
2_16.txt AC 3 ms 1408 KB
2_17.txt AC 3 ms 1280 KB
2_18.txt AC 3 ms 1280 KB
2_19.txt AC 3 ms 1408 KB
2_20.txt AC 3 ms 1280 KB
2_21.txt AC 3 ms 1280 KB
2_22.txt AC 3 ms 1536 KB