結果
問題 | No.421 しろくろチョコレート |
ユーザー |
![]() |
提出日時 | 2016-09-09 23:07:52 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 2,087 bytes |
コンパイル時間 | 1,597 ms |
コンパイル使用メモリ | 96,640 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-23 07:05:38 |
合計ジャッジ時間 | 2,924 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 65 |
ソースコード
#include <algorithm>#include <cstdio>#include <ctype.h>#include <functional>#include <iostream>#include <iomanip>#include <cassert>#include <cfloat>#include <climits>#include <complex>#include <cstdlib>#include <cstring>#include <cmath>#include <map>#include <queue>#include <set>#include <sstream>#include <stack>#include <string>#include <time.h>#include <vector>using namespace std;typedef vector<vector<int> > graph;struct BGM {int L, R; //左右のノード数graph g;vector<int> r2l; //右->左への対応BGM(int L, int R) : L(L), R(R), g(L), r2l(R, -1) {}void add_edge(int l, int r) {g[l].push_back(r);}bool augment(int l, vector<bool>& visited) {if (l == -1) return true;if (visited[l]) return false;visited[l] = true;vector<int>& e = g[l];for (int i = 0; i < e.size(); i++) {int r = e[i];if (augment(r2l[r], visited)) {r2l[r] = l;return true;}}return false;}int match() {int cnt = 0;for (int l = 0; l < L; l++) {vector<bool> visited(L);if (augment(l, visited)) ++cnt;}return cnt;}};int main() {int N,M;cin >> N >> M;vector<string> S(N);int t[50][50];int b=0;int w=0;for (int i = 0; i < N; i++) {cin >> S[i];}for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (S[i][j] == 'b') {t[i][j] = b;b++;}else if (S[i][j] == 'w') {t[i][j] = w;w++;}}}BGM bgm(b, w);for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (i < N - 1) {if (S[i][j] == 'b'&&S[i + 1][j] == 'w') {bgm.add_edge(t[i][j], t[i + 1][j]);}if (S[i][j] == 'w'&&S[i + 1][j] == 'b') {bgm.add_edge(t[i + 1][j], t[i][j]);}}if (j < M - 1) {if (S[i][j] == 'b'&&S[i][j + 1] == 'w') {bgm.add_edge(t[i][j], t[i][j + 1]);}if (S[i][j] == 'w'&&S[i][j + 1] == 'b') {bgm.add_edge(t[i][j + 1], t[i][j]);}}}}int a = bgm.match();b = b - a;w = w - a;int v = min(b, w);int r = b + w - 2 * v;cout << a * 100 + v * 10 + r << endl;return 0;}