이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e3 + 5;
const int MAXS = 3e6 + 5;
const int INF = 0x3f3f3f3f;
int N, M;
char mat[MAXN][MAXN];
vector <int> E[MAXS];
int match[MAXS], dist[MAXS];
int hor[MAXN][MAXN], ver[MAXN][MAXN];
vector <int> lft, rig;
void load() {
scanf("%d%d", &N, &M);
for (int i = 0; i < N; i++)
scanf("%s", mat[i]);
}
bool bfs() {
queue <int> Q;
for (auto it : lft)
if (!match[it]) {
dist[it] = 0;
Q.push(it);
}
else
dist[it] = INF;
dist[0] = INF;
while (!Q.empty()) {
int x = Q.front();
Q.pop();
if (!x)
continue;
for (auto it : E[x])
if (dist[match[it]] == INF) {
dist[match[it]] = dist[x] + 1;
Q.push(match[it]);
}
}
return dist[0] != INF;
}
bool dfs(int x) {
if (!x)
return true;
for (auto it : E[x])
if (dist[match[it]] == dist[x] + 1 && dfs(match[it])) {
match[it] = x;
match[x] = it;
return true;
}
dist[x] = INF;
return false;
}
int hopcroft_karp() {
int matching = 0;
while (bfs())
for (auto it : lft)
matching += !match[it] && dfs(it);
return matching;
}
int get(int x, int y) {
return M * x + y + 1;
}
void check_hor(int x, int y) {
if (y > M - 3)
return;
for (int i = 0; i < 3; i++)
if (mat[x][y + i] != "RGW"[i])
return;
lft.push_back(get(x, y));
for (int i = 0; i < 3; i++)
hor[x][y + i] = get(x, y);
}
void check_ver(int x, int y) {
if (x > N - 3)
return;
for (int i = 0; i < 3; i++)
if (mat[x + i][y] != "RGW"[i])
return;
rig.push_back(get(x, y));
for (int i = 0; i < 3; i++)
ver[x + i][y] = get(x, y);
}
int solve() {
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++) {
check_hor(i, j);
check_ver(i, j);
}
sort(lft.begin(), lft.end());
sort(rig.begin(), rig.end());
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++) {
/*if (hor[i][j])
hor[i][j] = lower_bound(lft.begin(), lft.end(), hor[i][j]) - lft.begin() + 1;
if (ver[i][j])
ver[i][j] = lower_bound(rig.begin(), rig.end(), ver[i][j]) - rig.begin() + 1;*/
if (hor[i][j] && ver[i][j])
E[hor[i][j]].push_back(ver[i][j]);
}
return lft.size() + rig.size() - hopcroft_karp();
}
int main() {
load();
printf("%d\n", solve());
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
dango_maker.cpp: In function 'void load()':
dango_maker.cpp:16:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
^
dango_maker.cpp:18:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", mat[i]);
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |