#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define N +100500
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e9)
#define el '\n'
#define pii pair <int, int>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;
int f[302][302][302];
int n, m, i, j, b, B, len, ans, I, J, sx, sy;
char c[305][305];
queue <pair <int, pair <int, int> > > q;
vector < pair <int, pair <int, int> > > v[2], start;
bool mrk[305][305][305], mk[305][305][305];
void put(int i, int j, int b, int ni, int nj)
{
if (c[ni][nj] == '*') return;
int B = b;
if (c[ni][nj] == '(') B++;else
if (c[ni][nj] == ')') B--;
if (c[ni][nj] == '.' && mrk[ni][nj][B] && f[ni][nj][B] == f[i][j][b] && !mk[ni][nj][B])
{
mk[ni][nj][B] = 1;
q.push({ni, {nj, B}});
}
else if (mrk[ni][nj][B] && f[ni][nj][B] == f[i][j][b] + 1 && !mk[ni][nj][B])
{
mk[ni][nj][B] = 1;
q.push({ni, {nj, B}});
}
}
int main()
{
srand(time(0));
ios_base::sync_with_stdio(0);
iostream::sync_with_stdio(0);
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
// in("input.txt");
// out("output.txt");
cin >> n >> m;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
for (b = 0; b <= 300; b++)
f[i][j][b] = -1;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
cin >> c[i][j];
if (c[i][j] == 'M') f[i][j][0] = 0, sx = i, sy = j;
}
for (i = n; i >= 2; i--)
{
for (j = 1; j <= m; j++)
for (b = 0; b <= 300; b++)
{
if (f[i][j][b] == -1) continue;
for (int st = -1; st < 2; st++)
{
if (j + st >= 1 && j + st <= m && c[i - 1][j + st] != '*')
{
int B = b, len = f[i][j][b];
if (c[i - 1][j + st] == '(') B++, len++; else
if (c[i - 1][j + st] == ')') B--, len++;
if (B >= 0 && f[i - 1][j + st][B] < len)
f[i - 1][j + st][B] = len;
}
}
}
}
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
ans = max(ans, f[i][j][0]);
cout << ans << el;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
if (ans == f[1][j][0]) mrk[1][j][0] = 1;
for (i = 1; i < n; i++)
{
for (j = 1; j <= m; j++)
for (b = 0; b <= 300; b++)
{
if (!mrk[i][j][b]) continue;
for (int st = -1; st < 2; st++)
{
int ni = i + 1, nj = j + st;
if (nj < 1 || nj > m) continue;
if (c[ni][nj] == '*') continue;
// cerr << ni << " " << nj << " " << i << " " << j << " " << f[i][j][b] << el;
if (c[i][j] == '(' && b > 0 && f[ni][nj][b - 1] + 1 == f[i][j][b]) mrk[ni][nj][b - 1] = 1;
else if (c[i][j] == ')' && f[ni][nj][b + 1] + 1 == f[i][j][b]) mrk[ni][nj][b + 1] = 1;
else if (f[ni][nj][b] == f[i][j][b] && c[i][j] == '.') mrk[ni][nj][b] = 1;
}
}
}
start.pb({sx, {sy, 0}});
for (int len = 0; len < ans; len++)
{
v[0].clear();
v[1].clear();
for (auto pos : start)
{
i = pos.F;
j = pos.S.F;
b = pos.S.S;
for (int st = -1; st < 2; st++)
{
int ni = i - 1;
int nj = j + st;
if (nj < 1 || nj > m) continue;
put(i, j, b, ni, nj);
}
}
while (sz(q))
{
i = q.front().F;
j = q.front().S.F;
b = q.front().S.S;q.pop();
if (c[i][j] == '(')
{
v[0].pb({i, {j, b}});
continue;
}
if (c[i][j] == ')')
{
v[1].pb({i, {j, b}});
continue;
}
for (int st = -1; st < 2; st++)
{
int ni = i - 1;
int nj = j + st;
if (nj < 1 || nj > m) continue;
put(i, j, b, ni, nj);
}
}
if (sz(v[0]) > 0)
{
start = v[0];
cout << "(";
}
else
{
start = v[1];
cout << ")";
}
}
}
/*
8 8
...).).*
*....)..
.)*(..).
(*)((...
.)).)(..
.)(.)..(
...).(.*
M.......
*/
//
//110000
//1100
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
896 KB |
Output is correct |
| 3 |
Correct |
5 ms |
768 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
7 ms |
2304 KB |
Output is correct |
| 6 |
Correct |
12 ms |
6912 KB |
Output is correct |
| 7 |
Correct |
15 ms |
9984 KB |
Output is correct |
| 8 |
Correct |
10 ms |
5760 KB |
Output is correct |
| 9 |
Correct |
15 ms |
10496 KB |
Output is correct |
| 10 |
Correct |
24 ms |
13696 KB |
Output is correct |
| 11 |
Correct |
141 ms |
105336 KB |
Output is correct |
| 12 |
Correct |
135 ms |
103672 KB |
Output is correct |
| 13 |
Correct |
65 ms |
49656 KB |
Output is correct |
| 14 |
Correct |
63 ms |
47736 KB |
Output is correct |
| 15 |
Correct |
154 ms |
112504 KB |
Output is correct |
| 16 |
Correct |
147 ms |
110968 KB |
Output is correct |
| 17 |
Correct |
130 ms |
95480 KB |
Output is correct |
| 18 |
Correct |
127 ms |
93304 KB |
Output is correct |
| 19 |
Correct |
160 ms |
110328 KB |
Output is correct |
| 20 |
Correct |
161 ms |
112504 KB |
Output is correct |
