paste bin
Author
Language
C++
Plain text
Accesslog
Action script
Ada
Apache
Arduino
Armasm
Autohotkey
Awk
Bash
Basic
Brainfuck
C
Clojure
Cmake
C#
css
D
Delphi
Dockerfile
Erlang
Fortran
F#
Gauss
Go
Gradle
Graphql
Groovy
Haskell
Ini
Java
JavaScript
json
Julia
Kotlin
Lasso
LaTeX
Leaf
lisp
llvm
Lua
Makefile
Markdown
Mathematica
Matlab
Nginx
Objective-C
Ocaml
Oxygene
Perl
PgSQL
php
Powershell
Processing
Profile
Properties
Puppet
Purebasic
Python
Q
QML
R
Ruby
Rust
Scala
Scheme
Scilab
Shell
Smalltalk
SQL
Swift
Typescript
VB.NET
VB Script
Verilog
Vim
Wasm
x86asm
Xml
Xquery
Yaml
source code:
#include <cstdio> #include <cstring> #include <set> using std::set; #include <queue> using std::queue; int str2int(char*); void num2Graph(int); int moveUp(int); int moveDown(int); int moveLeft(int); int moveRight(int); int solve(int); int inversions(char*); struct numNode { int level; int val; }; int main(void) { int IDX,i,N,v; N=1; char s[10]; for(IDX=1;IDX<=N;IDX++) { for(i=0;i<9;i++) scanf("%s",s+i); s[9]=0; if(inversions(s)%2==0) { v=str2int(s); printf("%d\n",solve(v) ); } else { printf("impossible\n"); } } return 0; } int inversions(char* s) { int count,i,j; count=0; for(i=1;i<9;i++) { for(j=0;j<i;j++) { if(s[j]=='0') continue; if(s[j]<s[i]) count++; } } return count; } int solve(int v) { set<int> used; queue<numNode> q; int (*move[4])(int)={moveUp,moveDown,moveLeft,moveRight}; int nextXVal,brkFlag,k,res; numNode x,nextX; x.level=0; x.val=v; q.push(x); used.insert(x.val); brkFlag=1; while(!q.empty()) { x=q.front(); q.pop(); if(x.val==123456780) { res=x.level; break; } for(k=0;k<4;k++) { nextXVal=move[k](x.val); nextX.level=x.level+1; if(nextXVal==123456780) { brkFlag=0; res=nextX.level; break; } if(used.count(nextXVal)==0) { nextX.val=nextXVal; q.push(nextX); used.insert(nextXVal); } } if(brkFlag==0) break; } return res; } int str2int(char* s) { int i,x=0; for(i=0;i<9;i++) { x=x*10+s[i]-'0'; } return x; } int moveUp(int x) { char s[10]; int tt,k; tt=1; for(k=8;k>=0;--k) { s[k]='0'+x%(10*tt)/tt; tt*=10; } int tmp,pos0,posZ; pos0=strchr(s,'0')-s; posZ=pos0-3; if(posZ>=0) { tmp=s[pos0]; s[pos0]=s[posZ]; s[posZ]=tmp; } return str2int(s); } int moveDown(int x) { char s[10]; int tt,k; tt=1; for(k=8;k>=0;--k) { s[k]='0'+x%(10*tt)/tt; tt*=10; } int tmp,pos0,posZ; pos0=strchr(s,'0')-s; posZ=pos0+3; if(posZ<9) { tmp=s[pos0]; s[pos0]=s[posZ]; s[posZ]=tmp; } return str2int(s); } int moveLeft(int x) { char s[10]; int tt,k; tt=1; for(k=8;k>=0;--k) { s[k]='0'+x%(10*tt)/tt; tt*=10; } int tmp,pos0,posZ; pos0=strchr(s,'0')-s; posZ=pos0-1; if(posZ>=0 && posZ%3<2) { tmp=s[pos0]; s[pos0]=s[posZ]; s[posZ]=tmp; } return str2int(s); } int moveRight(int x) { char s[10]; int tt,k; tt=1; for(k=8;k>=0;--k) { s[k]='0'+x%(10*tt)/tt; tt*=10; } int tmp,pos0,posZ; pos0=strchr(s,'0')-s; posZ=pos0+1; if(posZ%3>0) { tmp=s[pos0]; s[pos0]=s[posZ]; s[posZ]=tmp; } return str2int(s); }
comment: