用户输出
4
系统信息
Exited with return code 0| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #219 | #1038. 1-04E. zzj & liaoy 想要去摄影 | Accepted | 100 | 1235 ms | 21324 K | C++ 11 / 1.2 K | foreyes1001 | 2019-06-20 20:04:19 |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
map<tuple<int, int, int>, int> vis;
int Map[maxn][maxn];
int dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 };
int main() {
int n, m, cnt = 0, sx, sy;
cin >> n >> m;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++) {
if (s[j] == 'p') {
sx = i;
sy = j;
}
if (s[j] == '#') {
Map[i][j] = -1;
}
if (s[j] == '@') {
Map[i][j] = ++cnt;
}
}
}
int target = (1 << cnt) - 1, ans = -1;
tuple<int, int, int> start = make_tuple(sx, sy, 0);
queue<tuple<int, int, int> > q;
vis[start] = 0;
q.push(start);
while (!q.empty()) {
int x, y, state, step;
tie(x, y, state) = q.front();
step = vis[q.front()];
q.pop();
if (state == target) {
ans = step;
break;
}
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir], ny = y + dy[dir], nxt_state = state;
if (nx < 0 || ny < 0 || nx >= n || ny >= m || Map[nx][ny] == -1)
continue;
if (Map[nx][ny] != 0)
nxt_state |= (1 << (Map[nx][ny] - 1));
tuple<int, int, int> nxt = make_tuple(nx, ny, nxt_state);
if (vis.count(nxt) != 0)
continue;
vis[nxt] = step + 1;
q.push(nxt);
}
}
cout << ans << endl;
return 0;
}10 10
#.########
####.###@#
##########
######.###
@.#.#p#@##
###..##.##
##.#####.#
#.####@#.#
###@##
<15 bytes omitted>用户输出
-1
系统信息
Exited with return code 010 10
.##.@.#.#.
###..##@#.
...#@#.###
.#.#..#...
#..#.....#
....##..##
..##..@.#p
##....##..
..#...
<15 bytes omitted>用户输出
-1
系统信息
Exited with return code 010 10
.#@......#
...#......
..#.....##
..#..#....
...##..@.@
...@#.#...
#.#..#..#.
.p......##
.#..#.
<15 bytes omitted>用户输出
30
系统信息
Exited with return code 020 20
..##.......@........
..#...#....#..##....
...#.#...#..#.#..#..
..#...#..#@###..##..
..#.#....#
<325 bytes omitted>用户输出
61
系统信息
Exited with return code 030 30
##..##.###........#...#...@##.
#.#..#...##.....#.#.#..##p.#.@
...#.##......#...#.#.....#..#@
#
<835 bytes omitted>用户输出
12
系统信息
Exited with return code 030 30
.....#..#...#.@..#..##.#..#...
.#..##.....##..........#.....#
##...##...#.#.......p...#...#.
#
<835 bytes omitted>用户输出
83
系统信息
Exited with return code 030 30
##.....#.......#.....##...#@..
.......#.##.##..#.#.####.##...
.##......#..#.#.......#.....#.
.
<835 bytes omitted>用户输出
130
系统信息
Exited with return code 030 30
...#..###.....##.#....#...##..
#.#...#..#.#..#..#.######..##.
.##..#.@.#......##...#....#.#.
.
<835 bytes omitted>用户输出
154
系统信息
Exited with return code 030 30
..#...#...#...#........#....##
#.##....##.@#.#.#.#.#..@......
#.....#..@....#..#..##.#..#..#
.
<835 bytes omitted>用户输出
114
系统信息
Exited with return code 030 30
#.######.##.####.#######.#####
##.@####.######.#########.##.#
...######.########.########.##
#
<835 bytes omitted>用户输出
-1
系统信息
Exited with return code 0