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
#include
#include
#include
using namespace std; int n, m; char mat[105][105]; bool visited[105][105]; int bfs(int si, int sj, int ei, int ej) { for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { visited[i][j] = false; } } queue
q; q.push(si); q.push(sj); q.push(0); visited[si][sj] = true; 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 !visited[ci + 1][cj] and mat[ci + 1][cj] != '#') { q.push(ci + 1); q.push(cj); q.push(dist + 1); visited[ci + 1][cj ] = true; } if(ci - 1 >= 0 and !visited[ci - 1][cj] and mat[ci - 1][cj] != '#') { q.push(ci - 1); q.push(cj); q.push(dist + 1); visited[ci - 1][cj ] = true; } if(cj + 1 < m and !visited[ci][cj + 1] and mat[ci][cj + 1] != '#') { q.push(ci); q.push(cj + 1); q.push(dist + 1); visited[ci][cj + 1] = true; } if(cj - 1 >= 0 and !visited[ci][cj - 1] and mat[ci][cj - 1] != '#') { q.push(ci); q.push(cj - 1); q.push(dist + 1); visited[ci][cj- 1 ] = true; } } return -1; } int main() { cin >> n >> m; pair
idx[5]; int tmp = 1; int drinks = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cin >> mat[i][j]; if(mat[i][j] == 'S'){ idx[0] = make_pair(i, j); } if(mat[i][j] == 'D') { idx[tmp] = make_pair(i, j); drinks++; tmp++; } if(mat[i][j] == 'B') { idx[4] = make_pair(i, j); } } } int perm[drinks + 1]; for(int i = 0; i < drinks; i++) { perm[i] = i + 1; } int si = idx[0].first; int sj = idx[0].second; int bi = idx[4].first; int bj = idx[4].second; int result = 2e9; do { int p = 0; for(int i = 0; i < drinks; i++) { if(i == 0) { int x = bfs(si, sj, idx[perm[i]].first, idx[perm[i]].second); if(x == -1) { cout << -1 << endl; return 0; } p += x; } else { int x = bfs(idx[perm[i - 1]].first, idx[perm[i - 1]].second, idx[perm[i]].first, idx[perm[i]].second); if(x == -1) { cout << -1 << endl; return 0; } p += x; } } int x= bfs(idx[perm[drinks - 1]].first, idx[perm[drinks - 1]].second, bi, bj) ; if(x == -1) { cout << -1 << endl; return 0; } p += x; if(result > p) { result = p; } } while(next_permutation(perm, perm + drinks)); cout << result << endl; // S 1 2 3 B return 0; }
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)