//#include <iostream>
//#include <vector>
//using namespace std;
//using ll = long long;
//vector<vector<vector<ll>>> dp;
//vector<int> state;
//void dfs(int u, int p, vector<vector<int>>& gp)
//{
// ll sum1 = 0, cnt1 = 0, mn1 = 1e18, sum2 = 0, cnt2 = 0, mn2 = 1e18;
// for (int v : gp[u]) {
// if (v == p) continue;
//
// dfs(v, u, gp);
// if (dp[v][1][0] <= dp[v][0][0]) {
// sum1 += dp[v][1][0];
// ++cnt1;
// }
// else {
// sum1 += dp[v][0][0];
// }
// mn1 = min(mn1, abs(dp[v][1][0] - dp[v][0][0]));
// if (dp[v][1][1] <= dp[v][0][1]) {
// sum2 += dp[v][1][1];
// ++cnt2;
// }
// else {
// sum2 += dp[v][0][1];
// }
// mn2 = min(mn2, abs(dp[v][1][1] - dp[v][0][1]));
//
// }
// if (gp[u].size() == 1 && u != 0) {
// if (!state[u]) {
// dp[u][1][0] = 1;
// dp[u][0][0] = 1e18;
// dp[u][1][1] = 1e18;
// dp[u][0][1] = 0;
// }
// else {
// dp[u][1][0] = 1e18;
// dp[u][0][0] = 0;
// dp[u][1][1] = 1;
// dp[u][0][1] = 1e18;
// }
// return;
// }
// if (cnt1 % 2 != state[u]) {
// dp[u][0][0] = sum1;
// }
// else {
// dp[u][0][0] = sum1 + mn1;
// }
// state[u] = !state[u];
// if (cnt2 % 2 != state[u]) {
// dp[u][1][0] = sum2 + 1;
// }
// else {
// dp[u][1][0] = sum2 + mn2 + 1;
// }
// if (cnt1 % 2 != state[u]) {
// dp[u][0][1] = sum1;
// }
// else {
// dp[u][0][1] = sum1 + mn1;
// }
// state[u] = !state[u];
// if (cnt2 % 2 != state[u]) {
// dp[u][1][1] = sum2 + 1;
// }
// else {
// dp[u][1][1] = sum2 + mn2 + 1;
// }
//}
//
//void solve()
//{
// string a(45, '0');
// string b(34, '1');
// string res = a;
// res += b;
// res += "10111110001000100000011010001001100001011100101000011101111100010000000011000101110011110";
// int boris = 0, hayk = 0;
// for (int i = 0; i < res.size(); ++i) {
// if (res[i] == '0') ++hayk;
// else ++boris;
// }
// cout << hayk << " " << boris << "\n";
//}
//int main()
//{
// //int t; cin >> t; while (t--)
// solve();
//}
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <map>
#include <string>
#include <ios>
#include <iomanip>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(NULL);
using ll = long long;
using namespace std;
void solve() {
int n, m; cin >> n >> m;
vector<string>v(n);
vector<vector<int>>a(n, vector<int>(m));
vector<vector<int>>b(n, vector<int>(m));
vector<vector<int>>c(n, vector<int>(m));
vector<vector<int>>d(n, vector<int>(m));
vector<vector<int>>pref(n, vector<int>(m));
for (int i = 0; i < n; i++) {
cin >> v[i];
}
for (int i = 0; i < n; i++) {
if (v[i][0] == '#') {
pref[i][0] = 1;
}
for (int j = 1; j < m; j++) {
if (v[i][j] == '#') {
pref[i][j] = pref[i][j - 1] + 1;
}
else pref[i][j] = pref[i][j - 1];
}
}
// 7 10
// .....#...
// ....#.#..
// ...#...#.
// ..#.....#
// ...#...#.
// ....#.#..
// .....#...
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (j != 0 && i != n - 1 && j != m - 1) {
if (v[i + 1][j - 1] == '#' && v[i + 1][j + 1] == '#' && v[i + 1][j] == '.' && v[i][j] == '#') {
a[i + 1][j - 1] = 1;
b[i + 1][j + 1] = 1;
}
}
if (j != 0 && i != 0 && j != m - 1) {
if (v[i - 1][j - 1] == '#' && v[i - 1][j + 1] == '#' && v[i - 1][j] == '.' && v[i][j] == '#') {
c[i - 1][j - 1] = 1;
d[i - 1][j + 1] = 1;
}
}
}
}
for (int i = 0; i < n; i++) {
int arajin = -1, erkrord = -1, cnt = 0;
for (int j = 0; j < m; j++) {
if (v[i][j] == '#' && cnt == 0) {
cnt++;
arajin = j;
}
else if (v[i][j] == '#' && cnt == 1) {
if (i >= 1 && a[i - 1][arajin + 1] == 1 && b[i - 1][j - 1] == 1 && (pref[i - 1][j - 1] - pref[i - 1][arajin]) == 0) {
a[i][arajin] = 1;
b[i][j] = 1;
}
arajin = j;
}
}
}
for (int i = n - 1; i >= 0; i--) {
int arajin = -1, erkrord = -1, cnt = 0;
for (int j = 0; j < m; j++) {
if (v[i][j] == '#' && cnt == 0) {
cnt++;
arajin = j;
}
else if (v[i][j] == '#' && cnt == 1) {
if (i <= n - 2 && c[i + 1][arajin + 1] == 1 && d[i + 1][j - 1] == 1 && (pref[i + 1][j - 1] - pref[i + 1][arajin]) == 0) {
c[i][arajin] = 1;
d[i][j] = 1;
}
arajin = j;
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
int cnt = 0;
int arajin = -1, erkrord = -1;
for (int j = 0; j < m; j++) {
if (v[i][j] == '#' && cnt == 0) {
cnt++;
arajin = j;
}
else if (v[i][j] == '#' && cnt == 1) {
if (a[i][arajin] == 1 && c[i][arajin] == 1 && b[i][j] == 1 && d[i][j] == 1) {
ans++;
}
arajin = j;
}
}
}
cout << ans << endl;
}
}
signed main() {
FASTIO
ll t = 1;
//cin >> t;
while (t--) {
solve();
}
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:159:22: warning: unused variable 'erkrord' [-Wunused-variable]
159 | int arajin = -1, erkrord = -1, cnt = 0;
| ^~~~~~~
Main.cpp:193:24: warning: unused variable 'erkrord' [-Wunused-variable]
193 | int arajin = -1, erkrord = -1;
| ^~~~~~~
Main.cpp:175:22: warning: unused variable 'erkrord' [-Wunused-variable]
175 | int arajin = -1, erkrord = -1, cnt = 0;
| ^~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
