Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
#include
#include
#include
using namespace std; int n, m; char mat[105][105]; int bfs(int si, int sj, int ei, int ej) { queue
q; q.push(si); q.push(sj); q.push(0); vector
> visited(n, vector
(m, false)); while(!q.empty()) { int ci = q.front(); q.pop(); int cj = q.front(); q.pop(); int dist = q.front(); q.pop(); if(ci == ei and cj == ej) { return dist; } if(ci + 1 < n and mat[ci + 1][cj] != '#' and !visited[ci + 1][cj]) { q.push(ci + 1); q.push(cj); q.push(dist + 1); visited[ci + 1][cj] = true; } if(ci - 1 >= 0 and mat[ci - 1][cj] != '#' and !visited[ci - 1][cj]) { q.push(ci - 1); q.push(cj); q.push(dist + 1); visited[ci - 1][cj] = true; } if(cj + 1 < m and mat[ci][cj + 1] != '#' and !visited[ci][cj + 1]) { q.push(ci); q.push(cj + 1); q.push(dist + 1); visited[ci][cj + 1] = true; } if(cj - 1 >= 0 and mat[ci][cj - 1] != '#' and !visited[ci][cj - 1]) { q.push(ci); q.push(cj - 1); q.push(dist + 1); visited[ci][cj - 1] = true; } } return 1e8; } int main() { cin >> n >> m; vector
> d; int drinks = 0; int si, sj, ei, ej; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cin >> mat[i][j]; if(mat[i][j] == 'S') { si = i; sj = j; } if(mat[i][j] == 'B') { ei = i; ej = j; } if(mat[i][j] == 'D') { d.push_back(make_pair(i, j)); drinks++; } } } int res = 2e9; if(drinks == 1) { res = bfs(si, sj, d[0].first, d[0].second) + bfs(d[0].first, d[0].second, ei, ej); } else if(drinks == 2) { int r1 = bfs(si, sj, d[0].first, d[0].second) + bfs(d[0].first, d[0].second, d[1].first, d[1].second) + bfs(d[1].first, d[1].second, ei, ej); int r2 = bfs(si, sj, d[1].first, d[1].second) + bfs(d[1].first, d[1].second, d[0].first, d[0].second) + bfs(d[0].first, d[0].second, ei, ej); res = min(r1, r2); } else { int r1 = bfs(si, sj, d[0].first, d[0].second) + bfs(d[0].first, d[0].second, d[1].first, d[1].second) + bfs(d[1].first, d[1].second, d[2].first, d[2].second) + bfs(d[2].first, d[2].second, ei, ej); int r2 = bfs(si, sj, d[0].first, d[0].second) + bfs(d[0].first, d[0].second, d[2].first, d[2].second) + bfs(d[2].first, d[2].second, d[1].first, d[1].second) + bfs(d[1].first, d[1].second, ei, ej); int r3 = bfs(si, sj, d[1].first, d[1].second) + bfs(d[1].first, d[1].second, d[0].first, d[0].second) + bfs(d[0].first, d[0].second, d[2].first, d[2].second) + bfs(d[2].first, d[2].second, ei, ej); int r4 = bfs(si, sj, d[1].first, d[1].second) + bfs(d[1].first, d[1].second, d[2].first, d[2].second) + bfs(d[2].first, d[2].second, d[0].first, d[0].second) + bfs(d[0].first, d[0].second, ei, ej); int r5 = bfs(si, sj, d[2].first, d[2].second) + bfs(d[2].first, d[2].second, d[0].first, d[0].second) + bfs(d[0].first, d[0].second, d[1].first, d[1].second) + bfs(d[1].first, d[1].second, ei, ej); int r6 = bfs(si, sj, d[2].first, d[2].second) + bfs(d[2].first, d[2].second, d[1].first, d[1].second) + bfs(d[1].first, d[1].second, d[0].first, d[0].second) + bfs(d[0].first, d[0].second, ei, ej); res = min(min(r1, r2), min(r3, r4)); res = min(res, min(r5, r6)); } if(res > 1e8) { res = -1; } cout << res << endl; return 0; } /* 5 6 #S.### #...## .#..## D..B#. ##.#.. **/
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)