結果
問題 | No.348 カゴメカゴメ |
ユーザー |
|
提出日時 | 2016-03-05 17:25:38 |
言語 | C++11 (gcc 13.3.0) |
結果 |
MLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,643 bytes |
コンパイル時間 | 944 ms |
コンパイル使用メモリ | 80,900 KB |
実行使用メモリ | 814,336 KB |
最終ジャッジ日時 | 2024-09-24 14:22:31 |
合計ジャッジ時間 | 3,341 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 2 MLE * 1 -- * 50 |
ソースコード
#include<iostream>#include<vector>#include<set>#include<queue>#include<cstring>#define r first#define c secondusing namespace std;typedef pair<int, int> Point;const int BUF = 1005;int row, col;char b[BUF][BUF];void read() {cin >> row >> col;for (int i = 0; i < row + 2; ++i) {for (int j = 0; j < col + 2; ++j) {b[i][j] = '.';}}for (int i = 1; i <= row; ++i) {for (int j = 1; j <= col; ++j) {cin >> b[i][j];}}row += 2;col += 2;}bool isInside(int r, int c) {return 0 <= r && r < row && 0 <= c && c < col;}void traceRing(int r, int c, int curId, int ringId[BUF][BUF]) {static int dr[] = {-1, -1, -1, 0, 1, 1, 1, 0};static int dc[] = {-1, 0, 1, 1, 1, 0, -1, -1};ringId[r][c] = curId;for (int i = 0; i < 8; ++i) {int nr = r + dr[i];int nc = c + dc[i];if (isInside(nr, nc) && b[nr][nc] == 'x' && ringId[nr][nc] == -1) {traceRing(nr, nc, curId, ringId);}}}void colorArea(int initR, int initC, int currId, bool visited[BUF][BUF],vector< set<int> > &adjRing, int ringId[BUF][BUF]) {queue<Point> Q;Q.push(Point(initR, initC));visited[initR][initC] = true;while (!Q.empty()) {Point curr = Q.front();Q.pop();static int dr[] = {-1, 0, 1, 0};static int dc[] = {0, 1, 0, -1};for (int i = 0; i < 4; ++i) {int nr = curr.r + dr[i];int nc = curr.c + dc[i];if (!isInside(nr, nc)) continue;if (b[nr][nc] == 'x') {if (currId != ringId[nr][nc])adjRing[currId].insert(ringId[nr][nc]);}else if (!visited[nr][nc]) {Q.push(Point(nr, nc));visited[nr][nc] = true;}}}}int doDp(bool preUsed, int curr, vector< vector<int> > &dp,vector< set<int> > &adjRing, int ringId2cnt[BUF]) {int &ret = dp[preUsed][curr];if (ret != -1) return ret;int A = 0; // use currentint B = 0; // do not use currentfor (set<int>::iterator it = adjRing[curr].begin(); it != adjRing[curr].end(); ++it) {A += doDp(true, *it, dp, adjRing, ringId2cnt);B += doDp(false, *it, dp, adjRing, ringId2cnt);}return ret = (preUsed ? B : max(A + ringId2cnt[curr], B));}void work() {int nRing = 1;static int ringId[BUF][BUF];memset(ringId, -1, sizeof(ringId));for (int i = 0; i < row; ++i)for (int j = 0; j < col; ++j)if (b[i][j] == 'x' && ringId[i][j] == -1) {traceRing(i, j, nRing++, ringId);}static int ringId2cnt[BUF];memset(ringId2cnt, 0, sizeof(ringId2cnt));for (int i = 0; i < row; ++i)for (int j = 0; j < col; ++j)if (ringId[i][j] != -1) {++ringId2cnt[ringId[i][j]];}vector< set<int> > adjRing(nRing, set<int>());static bool visited[BUF][BUF];memset(visited, 0, sizeof(visited));colorArea(0, 0, 0, visited, adjRing, ringId);for (int i = 0; i < row; ++i)for (int j = 0; j < col; ++j)if (!visited[i][j] && ringId[i][j] != -1) {colorArea(i, j, ringId[i][j], visited, adjRing, ringId);}vector< vector<int> > dp(2, vector<int>(nRing, -1));cout << doDp(false, 0, dp, adjRing, ringId2cnt) << endl;}int main() {read();work();return 0;}