Untitled
unknown
plain_text
a year ago
2.9 kB
8
Indexable
#include<iostream> using namespace std; #define sach 0 #define ban 1 #define chuongngai 2 #define rbbandau 3 const int maxq=10000; // thu vien str copy void strcpy(char *src, char *dst){ int i=0; while( src[i]!='\0'){ dst[i]=src[i++]; } dst[i]='\0'; } struct pos{ int x,y; }; struct Queue{ pos q[maxq]; int top; int bot; Queue(){ top=-1; bot=-1; } void reset(){ top=-1; bot=-1; } void push(pos value){ q[++top%maxq]=value; } pos pop(){ if(top!=bot) return q[++bot%maxq]; } pos peek(){ if(top!=bot) return q[bot++%maxq]; } bool isempty(){ return bot==top; } }; int m,n,idx,sum,answer; int map[105][105]; int visit[105][105]; int visit2[15]; int ke[15][15]; int oban[2][15]; bool flag; int dx[4]={-1,0,1,0}; int dy[4]={0,-1,0,1}; // luu vi tri void resetvisit(){ for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ visit[i][j]=0; } } } void resetvisit2(){ for(int i=0;i<idx;i++){ visit2[i]=0; } } int checkvisit2(){ for(int i=0;i<idx;i++){ if(visit2[i]==0)return 0; } return 1; // neu ghe tham het cac o ban } void tinh(int x,int count){ if(count==idx && checkvisit2()){ if(sum<answer) answer=sum; } if(sum>answer)return; for(int i=0;i<idx;i++){ if(!visit2[i]){ sum+=ke[x][i]; visit2[i]=1; tinh(i,count+1); sum-=ke[x][i]; visit2[i]=0; } } } void bfs(int r,int c,int index){ Queue q=Queue(); pos el={r,c}; q.push(el); visit[r][c]=1; while(!q.isempty()){ pos top=q.pop(); for(int i=0;i<4;i++){ int x=top.x+dx[i]; int y=top.y+dy[i]; if(x>=0 && x<n&& y>=0 &&y<m&& visit[x][y]==0 && map[x][y]!=2) { visit[x][y]=visit[top.x][top.y]+1; pos el={x,y}; q.push(el); } } } // ma tran ke voi hang la index cot lan luot la vi tri o ban for(int i=0;i<idx;i++){ ke[index][i]=visit[oban[0][i]][oban[1][i]]-1; if(ke[index][i]==-1) flag=true;// o visit bang 0 tuc laf khong loang vaof dc } } int main(){ FILE*file; freopen_s(&file,"input.txt","r",stdin); int t; cin>>t; for(int testcase =1;testcase<=t;testcase++){ flag=false; //nhap mang cin >>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>map[i][j]; } } // thuc hien idx=1; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(map[i][j]==3){ oban[0][0]=i;// vt robot oban[1][0]=j; } if(map[i][j]==1){ oban[0][idx]=i; oban[1][idx]=j;// dien xong moi cong nen khong lo vu <idx idx++; } } } // duyet ngang for (int i=0 ;i<idx;i++){ resetvisit(); bfs(oban[0][i],oban[1][i],i); } answer=9999999; sum=0; tinh(0,0); // out if(flag){ cout<<"Case #"<<testcase<<endl; cout<<-1<<endl; } else{ cout<<"Case #"<<testcase<<endl; cout<<answer<<endl; } } return 0; }
Editor is loading...
Leave a Comment