結果
| 問題 | No.348 カゴメカゴメ |
| ユーザー |
 Kmcode1
|
| 提出日時 | 2016-02-26 23:43:40 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 4,305 bytes |
| コンパイル時間 | 1,303 ms |
| コンパイル使用メモリ | 119,508 KB |
| 実行使用メモリ | 28,972 KB |
| 最終ジャッジ日時 | 2024-09-23 02:43:41 |
| 合計ジャッジ時間 | 6,577 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 42 RE * 11 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:203:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
203 | scanf("%s", room[i]);
| ~~~~~^~~~~~~~~~~~~~~
ソースコード
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cctype>#include<cstdlib>#include<algorithm>#include<bitset>#include<cstdio>#include<cstring>#include<string>#include<cctype>#include<cstdlib>#include<algorithm>#include<bitset>#include<vector>#include<list>#include<deque>#include<queue>#include<map>#include<set>#include<stack>#include<cmath>#include<sstream>#include<fstream>#include<iomanip>#include<ctime>#include<complex>#include<functional>#include<climits>#include<cassert>#include<iterator>using namespace std;#define MAX 1012int n;int m;char room[MAX][MAX];int dx[] = { 1, 1, 0, -1, -1, -1, 0, 1 };int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };struct st{vector < pair<int, int> > v;};vector<st> v;bool use[MAX][MAX];int deg[MAX];int id[MAX][MAX];bool valid(int x, int y){if (x < 0 || y < 0 || x >= n || y >= m){return false;}if (use[x][y]){return false;}if (room[x][y] == '.'){return false;}return true;}inline void dfs(int a, int b,int ii){use[a][b] = true;id[a][b] = ii;v[ii].v.push_back(make_pair(a, b));for (int i = 0; i < 8; i++){if (valid(a + dx[i], b + dy[i])){dfs(a + dx[i], b + dy[i],ii);}}}bool done[MAX];vector<int> g[MAX];bool s[MAX][MAX];int dxx[] = { 0, 0, 1, -1 };int dyy[] = { 1, -1, 0, 0 };bool vv(int a, int b){if (a < 0 || b < 0 || a >= n || b >= m){return false;}if (room[a][b] == '.'){return true;}return false;}bool v2(int a, int b){if (a < 0 || b < 0 || a >= n || b >= m){return false;}return true;}vector<int> bfs(int a, int b){vector<int> r;s[a][b] = true;queue<pair<int, int> > q;q.push(make_pair(a, b));while (!q.empty()){a = q.front().first;b = q.front().second;q.pop();for (int i = 0; i < 4; i++){int aa = a + dxx[i];int bb = b + dyy[i];if (vv(aa, bb)){if (s[aa][bb] == false){s[aa][bb] = true;q.push(make_pair(aa, bb));}}else{if (v2(aa, bb)){r.push_back(id[aa][bb]);}}}for (int i = 0; i < 8; i++){if (dx[i] == 0 || dy[i] == 0){continue;}if (vv(a + dx[i], b + dy[i])){if (v2(a, b + dy[i]) && vv(a, b + dy[i]) == false){if (v2(a + dx[i], b) && vv(a + dx[i], b) == false){r.push_back(id[a + dx[i]][b]);continue;}}if (s[a + dx[i]][b + dy[i]] == false){q.push(make_pair(a + dx[i], b + dy[i]));s[a + dx[i]][b + dy[i]] = true;}}else{if (v2(a + dx[i], b + dy[i])){r.push_back(id[a + dx[i]][b + dy[i]]);}}}}sort(r.begin(), r.end());r.erase(unique(r.begin(), r.end()), r.end());return r;}inline void f(int b){done[b] = true;set<int> vv;for (int i = 0; i < v[b].v.size(); i++){for (int j = 0; j < 8; j++){int xx = v[b].v[i].first + dx[j];int yy = v[b].v[i].second + dy[j];if (xx >= 0 && yy >= 0 && xx < n&&yy < m){if (room[xx][yy] == '.'){if (s[xx][yy] == false){vector<int> rr = bfs(xx, yy);for (int ii = 0; ii < rr.size(); ii++){vv.insert(rr[ii]);}}}}}}if (vv.count(b)){vv.erase(b);}for (auto it = vv.begin();it!= vv.end(); it++){g[b].push_back((*it));}vv.clear();for (int i = 0; i < g[b].size(); i++){f(g[b][i]);deg[g[b][i]]++;}}int dp[MAX][2];inline void d(int b){dp[b][0] = v[b].v.size();for (int i = 0; i < g[b].size(); i++){int id = g[b][i];d(id);dp[b][1] += max(dp[id][0], dp[id][1]);dp[b][0] += dp[id][1];}}int main(){cin >> n >> m;for (int i = 0; i < n; i++){scanf("%s", room[i]);}for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (valid(i, j)){v.push_back(st());dfs(i, j, v.size() - 1);}}}for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (i == 0 || j == 0 || i == n - 1 || j == m - 1){if (room[i][j] == '.'){if (s[i][j] == false){bfs(i, j);}}}}}for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (room[i][j] == 'x'){if (done[id[i][j]] == false){f(id[i][j]);}}}}int ans = 0;for (int i = 0; i < v.size(); i++){if (deg[i] == 0){d(i);ans += max(dp[i][0], dp[i][1]);}}cout << ans << endl;return 0;}