QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #190413 | #1952. Window Shopping | SolitaryDream# | AC ✓ | 59ms | 14520kb | C++20 | 3.8kb | 2023-09-28 20:38:22 | 2023-09-28 20:38:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 102;
int n, m;
string s[N];
map<int, int> f[N][N];
inline vector<int> Restore(int st, vector<int> &ans) {
ans.resize(m);
for (int i = 0; i < m; ++i) ans[i] = st % 10 - 1, st /= 10;
return ans;
}
inline int Calc(const vector<int> &a) {
int st = 0;
for (int i = m - 1; ~i; --i) st = st * 10 + a[i] + 1;
return st;
}
inline void SetMax(int &val, int x) {
val = max(val, x);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) cin >> s[i];
if (n < m) {
static string t[N];
for (int i = 0; i < n; ++i) t[i].swap(s[i]);
swap(n, m);
for (int i = 0; i < n; ++i) {
s[i].resize(m);
for (int j = 0; j < m; ++j) s[i][j] = t[j][i];
}
}
int pi = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (s[i][j] == 'U' || s[i][j] == 'D')
pi = i;
f[0][0][0] = 0;
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int ni = i, nj = j + 1;
if (nj == m) ni += 1, nj = 0;
// cout << i << ' ' << j << ' ' << f[i][j].size() << endl;
// printf("=> %d %d\n", ni, nj);
for (auto [st, num] : f[i][j]) {
do { // choose white
if (s[i][j] == '#') break;
vector<int> a;
Restore(st, a);
int n_num = num;
if (i && a[j] == -1 && s[i - 1][j] == '.' && s[i][j] == '.') ++n_num;
if (j && a[j - 1] == -1 && s[i][j - 1] == '.' && s[i][j] == '.') ++n_num;
if (a[j] == -1) a[j] = j;
if (j && a[j - 1] >= 0) {
int p1 = a[j - 1], p2 = a[j];
if (p1 != p2) a[max(p1, p2)] = min(p1, p2);
}
for (int i = 0; i < m; ++i) if (a[i] != -1) a[i] = a[a[i]];
int n_st = Calc(a);
SetMax(f[ni][nj][n_st], n_num);
} while (0);
do { // choose black
if (s[i][j] == 'U' || s[i][j] == 'D') break;
vector<int> a;
Restore(st, a);
int n_num = num;
if (i && a[j] >= 0 && s[i][j] != '#' && s[i - 1][j] == '.') ++n_num;
if (j && a[j - 1] >= 0 && s[i][j] != '#' && s[i][j - 1] == '.') ++n_num;
if (a[j] == j) {
vector<int> vec;
for (int p = j + 1; p < m; ++p) if (a[p] == j) vec.push_back(p);
if (vec.empty()) break;
for (auto p : vec) a[p] = vec.front();
a[j] = -1;
} else {
a[j] = -1;
}
int n_st = Calc(a);
SetMax(f[ni][nj][n_st], n_num);
} while(0);
}
}
if (i >= pi) {
for (auto [st, num] : f[i + 1][0]) {
vector<int> a;
Restore(st, a);
int occ = -1;
bool flag = 1;
for (int p = 0; p < m; ++p) if (a[p] >= 0) {
if (i + 1 < n && s[i][p] == '.' && s[i + 1][p] == '.') ++num;
if (occ == -1) occ = a[p];
if (a[p] != occ) { flag = 0; break; }
}
if (flag) {
// for (int p = 0; p < m; ++p) printf("%d ", a[p]);
// printf(" => %d\n", num);
ans = max(ans, num);
}
}
}
}
printf("%d\n", ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4300kb
input:
5 5 ..D#. .#... .#... .#... ..U#.
output:
10
result:
ok single line: '10'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4276kb
input:
5 5 U...# ...#. ..... .#... #...D
output:
14
result:
ok single line: '14'
Test #3:
score: 0
Accepted
time: 1ms
memory: 4276kb
input:
4 5 ..... ..#.. .#U#. ..D..
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4296kb
input:
5 4 .... .##. ..#. .#U# ...D
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4512kb
input:
2 5 .U.D. ..#.#
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4296kb
input:
2 10 #.....###. ..#.#.UD..
output:
3
result:
ok single line: '3'
Test #7:
score: 0
Accepted
time: 1ms
memory: 4284kb
input:
3 3 D.. ... ..U
output:
6
result:
ok single line: '6'
Test #8:
score: 0
Accepted
time: 1ms
memory: 4544kb
input:
3 3 #.. .U. ..D
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 1ms
memory: 4528kb
input:
5 4 .... .... ..U. .D.. ....
output:
16
result:
ok single line: '16'
Test #10:
score: 0
Accepted
time: 1ms
memory: 4544kb
input:
1 20 ##.............U.D.#
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Accepted
time: 1ms
memory: 4260kb
input:
20 1 # . . D . . . . . . . . U . . . . . . .
output:
2
result:
ok single line: '2'
Test #12:
score: 0
Accepted
time: 1ms
memory: 4336kb
input:
9 9 U#....... .#.#####. .#.#...#. .#.#.#.#. .#.#.#.#. .#.#.#.#. .#.#.#.#. .#.#.#.#. ...#D#...
output:
0
result:
ok single line: '0'
Test #13:
score: 0
Accepted
time: 3ms
memory: 4808kb
input:
9 11 ........... .###.#####. .#...#..D#. U#...#...#. .######.##. .#.......#. .#.......#. .###.#####. ...........
output:
19
result:
ok single line: '19'
Test #14:
score: 0
Accepted
time: 5ms
memory: 5092kb
input:
10 9 ......... ......... .#######. .#D#U#.#. .#.#.#.#. .#.#..... .#.###### .#....... ..######. .........
output:
16
result:
ok single line: '16'
Test #15:
score: 0
Accepted
time: 55ms
memory: 13660kb
input:
9 11 ........... ........... ........... ........... .....D..... ....U...... ........... ........... ...........
output:
111
result:
ok single line: '111'
Test #16:
score: 0
Accepted
time: 59ms
memory: 14520kb
input:
9 11 ........... ........... ........... ........... ........... ........... ........... ........... U.........D
output:
112
result:
ok single line: '112'
Test #17:
score: 0
Accepted
time: 3ms
memory: 4920kb
input:
11 9 ..#..#..# ..#..#... #..#..#.. #.D#..#.. ..#..#..# ..#..U..# #.....#.. #..#..#.. ..#..#..# ..#..#..# ..#.....#
output:
41
result:
ok single line: '41'
Test #18:
score: 0
Accepted
time: 5ms
memory: 5456kb
input:
9 11 ........... .#.#####... ..#....#... .#..#...#.. .#.#U#..#.. .#.#D...#.. .#..####... .#......... .#.#....#..
output:
35
result:
ok single line: '35'
Test #19:
score: 0
Accepted
time: 3ms
memory: 4700kb
input:
11 9 ......... .#.#####. ..#.#..#. .#..#...# .#.#D#..# .#.#..... .#..##.#. ........# .#######. ......... .#######U
output:
15
result:
ok single line: '15'
Test #20:
score: 0
Accepted
time: 5ms
memory: 5640kb
input:
9 11 .#.#.#.#.#. ........... .#.#.#.#.#. ........... .#.#.U.#.#. ........... .#.D.#.#.#. ........... .#.#.#.#.#.
output:
46
result:
ok single line: '46'
Test #21:
score: 0
Accepted
time: 2ms
memory: 4652kb
input:
9 11 ...#U#...## .#.....#... ##.#.#.#.## .#.#.#.#... .#.#.###### ...#.#..D.. .#.#.#.#.## .#.....#... .#.#.###.##
output:
13
result:
ok single line: '13'
Test #22:
score: 0
Accepted
time: 2ms
memory: 5136kb
input:
11 9 ......... ......... #####U### ......... ####.#### ......... #####...# ......... #####D### ......... ##....###
output:
32
result:
ok single line: '32'
Test #23:
score: 0
Accepted
time: 6ms
memory: 5588kb
input:
9 11 .#..#...#.# .#..#...#.# .#......D.. .#..#...#.. .U..#...#.. .#..#.#.#.. .#..#.#.#.# .#..#.#.#.# .#..#.#.#.#
output:
36
result:
ok single line: '36'
Test #24:
score: 0
Accepted
time: 2ms
memory: 4736kb
input:
9 11 ........... .#.######.. .#.#.#..#.. .#.#.#..#.. .#.#.#.#..# .#.#.#.#.#D .#.#.#.#.#. .#.#.#...#. .#U#.......
output:
12
result:
ok single line: '12'
Test #25:
score: 0
Accepted
time: 2ms
memory: 4876kb
input:
9 11 ........... .#########. .#......... .#.######## D#....U#... .#######... .#......... .#.######## ...........
output:
8
result:
ok single line: '8'
Test #26:
score: 0
Accepted
time: 0ms
memory: 4264kb
input:
9 11 ########### ########### ########### ########### ########### ########### #######UD## ########### ###########
output:
0
result:
ok single line: '0'
Test #27:
score: 0
Accepted
time: 9ms
memory: 5580kb
input:
9 11 ##.D#..#..# .##..#U#... ...#.#....# #.......... .#....#..#. ....#...... ..###..#... ....###...# .##........
output:
44
result:
ok single line: '44'
Test #28:
score: 0
Accepted
time: 10ms
memory: 5980kb
input:
9 11 ##..#.....# .....#...#. ...###...D. #.......##. #..U#...... ..#....##.. ..#....###. ........#.. ....#...#..
output:
56
result:
ok single line: '56'
Test #29:
score: 0
Accepted
time: 9ms
memory: 5864kb
input:
9 11 .....#.#... .#......... ..#.##....# ..#..#D..## ....#.....# ....#.#.##. ...#.....#U ......#.... ##.#.#....#
output:
50
result:
ok single line: '50'
Test #30:
score: 0
Accepted
time: 1ms
memory: 4644kb
input:
5 19 ....#....#..#..#.#. #........#..#..#... ..#...#.#....U..... .......D..#.....#.. .#.....#.#......#..
output:
56
result:
ok single line: '56'
Test #31:
score: 0
Accepted
time: 1ms
memory: 4340kb
input:
5 19 ......#....#.....## .#...........#.#.## #......#...U..#.#.# ..........#.#...#.. ....#..#.D.........
output:
52
result:
ok single line: '52'
Test #32:
score: 0
Accepted
time: 1ms
memory: 4416kb
input:
5 19 ................... .....#........##... .#..#...##.....#... #.......#...#..#... ..#.#.U.#.....D#...
output:
60
result:
ok single line: '60'
Test #33:
score: 0
Accepted
time: 2ms
memory: 4772kb
input:
16 6 ...... ..U#.. #..... .#.#.. ....#. #..... .....# .#.#.. ...... ...... #....# .....# .#D.#. ....#. ...... #.#...
output:
61
result:
ok single line: '61'
Test #34:
score: 0
Accepted
time: 2ms
memory: 4536kb
input:
16 6 ....#. #..... ##.#.. ...... ...... .....# ....D. ..#### ....## ..#... #...## ....U. ..#... ....#. ...... ....#.
output:
61
result:
ok single line: '61'
Test #35:
score: 0
Accepted
time: 2ms
memory: 4472kb
input:
16 6 .....# #.#... ...... .D.... #..#.. .#.... ...##. .....U .##... ...... .#..#. #..#.# .....# .....# ...... #..#..
output:
58
result:
ok single line: '58'
Test #36:
score: 0
Accepted
time: 1ms
memory: 4332kb
input:
5 5 ...U. ....D ..... ..... ...##
output:
20
result:
ok single line: '20'
Test #37:
score: 0
Accepted
time: 0ms
memory: 4272kb
input:
4 4 U.D. .... #.## #.##
output:
5
result:
ok single line: '5'