結果

問題 No.348 カゴメカゴメ
ユーザー HachimoriHachimori
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<cstring>
#define r first
#define c second
using 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 current
int B = 0; // do not use current
for (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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0