codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
// quan ma #include <iostream> using namespace std; int T, M, N, mang[105][105], check[105][105]; int toadox[105], toadoy[105], d[105][105], visit[105]; int queue[1000000]; int r, l,c, minx; void push(int n){ queue[++r]=n; } int pop(){ return queue[++l]; } int dx[8]={-1,-1,1,1,-2,-2,2,2}; int dy[8]={-2,2,-2,2,-1,1,-1,1}; int BFS(int x, int y){ int x1=toadox[x]; int y1=toadoy[x]; int x2=toadox[y]; int y2=toadoy[y]; for(int i=1; i<=N; i++){ for(int j=1; j<=M; j++){ check[i][j]=0; } } r=-1; l=-1; push(x1*1000+y1); check[x1][y1]=1; while(r!=l){ int tmp = pop(); int yyy=tmp%1000; int xxx=tmp/1000; for (int k=0; k<8; k++){ int yy = dy[k]+yyy; int xx = dx[k]+xxx; if(xx>0 &&yy>0 && xx<N+1 && yy<M+1){ if(check[xx][yy]==0 ){ if(xx==x2 && yy==y2){ return check[xxx][yyy]; } check[xx][yy]=check[xxx][yyy]+1; push(xx*1000+yy); } } } } } void backtrack(int x, int t, int s){ if(t==c){ if(s<minx) minx=s; return; } else{ for(int i=0; i<c; i++){ if(visit[i]==0){ visit[i]=1; if(s<minx){ backtrack(i, t+1, s+d[x][i]); } visit[i]=0; } } } } int main(){ //freopen("input.txt", "r", stdin); cin>>T; for(int t=1; t<=T; t++){ c=1; minx=99999999; cin>>N>>M; for(int i=1; i<=N; i++){ for(int j=1; j<=M; j++){ cin>>mang[i][j]; if(mang[i][j]==1) { toadox[c]=i; toadoy[c]=j; visit[c]=0; c++; } if(mang[i][j]==3) { toadox[0]=i; toadoy[0]=j; } } } for(int i=0; i<c-1; i++){ for(int j=i+1; j<c; j++){ d[j][i]=d[i][j]=BFS(i,j); } } /*for(int i=0; i<c; i++){ for(int j=0; j<c; j++){ cout<< d[i][j]<<" "; } cout<<endl; }*/ visit[0]=1; backtrack(0,1,0); cout<<"Case #"<<t<<endl<< minx<<endl; } return 0; }
Private
[
?
]
Run code
Submit