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; bool vis[16][16][15][(1<<10)]; int main() { memset(vis,0,sizeof vis); int n,m; cin >> n >> m; char mat[n][m]; int si,sj,ei,ej; int b=0; for(int i=0;i
> mat[i][j]; if(mat[i][j]=='S') { si=i; sj=j; } if(mat[i][j]=='E') { ei=i; ej=j; } if(mat[i][j]=='K') { mat[i][j]= (b+'0'); b++; } } } queue
Q; Q.push(si); Q.push(sj); Q.push(0);///K Q.push(0);///kojK Q.push(0);///kolku vis[si][sj][0][0]=true; int di[4]={1,-1,0,0}; int dj[4]={0,0,-1,1}; int dik[8]={-1,-1,1,1,2,2,-2,-2}; int djk[8]={-2,2,-2,2,-1,1,-1,1}; while(!Q.empty()) { int ci=Q.front(); Q.pop(); int cj=Q.front(); Q.pop(); int k=Q.front(); Q.pop(); int kojk=Q.front(); Q.pop(); int kolku=Q.front(); Q.pop(); if(ci==ei && cj==ej) { return kolku; } for(int i = 0; i < 4; i++) { int ti = di[i] + ci; int tj = dj[i] + cj; if(ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '*') { int new_k = k; int new_mask = kojk; if(isdigit(mat[ti][tj])) { int d = (mat[ti][tj] - '0'); if(new_mask & (1 << d)) { } else { new_mask |= (1 << d); new_k++; } } if(!vis[ti][tj][new_k][new_mask]) { Q.push(ti); Q.push(tj); Q.push(new_k); Q.push(new_mask); Q.push(kolku + 1); vis[ti][tj][new_k][new_mask] = true; } } } if(k > 0) { for(int i =0; i < 8; i++) { int ti = ci + dik[i]; int tj = cj + djk[i]; if(ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '*') { int new_k = k - 1; int new_mask = kojk; if(isdigit(mat[ti][tj])) { int d = (mat[ti][tj] - '0'); if(new_mask & (1 << d)) { } else { new_mask |= (1 << d); new_k++; } } if(!vis[ti][tj][new_k][new_mask]) { Q.push(ti); Q.push(tj); Q.push(new_k); Q.push(new_mask); Q.push(kolku + 1); vis[ti][tj][new_k][new_mask] = true; } } } } } cout << -1 << endl; return 0; } /* 4 5 ...*. ..*** ...K* S*E** **/
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)