1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | #include <iostream> #include <queue> #include <cstring> #include <unordered_map> using namespace std; int dy[4] = {0, 0, –1, 1}; int dx[4] = {1, –1, 0, 0}; int W, H, sy, sx; char graph[101][101]; bool visited[101][101][1 << 10] = {false}; unordered_map<string, int> trash; struct Node { int y, x, p; }; int bfs() { queue<Node> q; visited[sy][sx][0] = true; q.push({sy, sx, 0}); int result = 0; while (!q.empty()) { auto s = q.size(); while (s––) { Node n = q.front(); q.pop(); if (n.p == (1 << trash.size()) – 1) return result; for (int i = 0; i < 4; i++) { int ny = n.y + dy[i]; int nx = n.x + dx[i]; int tp = n.p; if (ny < 0 or nx < 0 or ny >= H or nx >= W) continue; if (graph[ny][nx] == ‘x’) continue; if (graph[ny][nx] == ‘*’) tp |= 1 << trash[to_string(ny) + “-“ + to_string(nx)]; if (!visited[ny][nx][tp]) { visited[ny][nx][tp] = true; q.push({ny, nx, tp}); } } } result++; } return –1; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); while (true) { int no = 0; trash = unordered_map<string, int>(); cin >> W >> H; if (W == 0 and H == 0) break; memset(graph, 0, sizeof(graph)); memset(visited, 0, sizeof(visited)); for (int i = 0; i < H; i++) { cin >> graph[i]; for (int j = 0; j < W; j++) { if (graph[i][j] == ‘o’) { sy = i; sx = j; } if (graph[i][j] == ‘*’) trash[to_string(i) + “-“ + to_string(j)] = no++; } } cout << bfs() << “\n”; } return 0; } | cs |