Untitled
unknown
plain_text
2 years ago
6.9 kB
12
Indexable
Hugo_ditau #include <iostream> using namespace std; int N; struct node{ int P; int C; }Door[5]; int check[100];// mang dung de luu gia tri vi nao len cua nao int Min; int Q[50000]; int front, rear; int Door1[100]; int Door2[100]; int Door3[100]; int A[4]; int checkBFS[100]; // Mang dung de check BFS void Create() { Door1[Door[1].P] = 1; for(int i=Door[1].P; i>1;i--) Door1[i-1] = Door1[i]+1; for(int i=Door[1].P; i<N;i++) Door1[i+1] = Door1[i]+1; Door2[Door[2].P] = 1; for(int i=Door[2].P; i>1;i--) Door2[i-1] = Door2[i]+1; for(int i=Door[2].P; i<N;i++) Door2[i+1] = Door2[i]+1; Door3[Door[3].P] = 1; for(int i=Door[3].P; i>1;i--) Door3[i-1] = Door3[i]+1; for(int i=Door[3].P; i<N;i++) Door3[i+1] = Door3[i]+1; } void BFS_trai(int vt, int dem) { for(int i=0;i<=N;i++) checkBFS[i] = 0; front = rear = 0; Q[rear] = vt; checkBFS[vt] = 1; rear++; if(check[vt] == 0) { check[vt] = vt; dem--; } while (front<rear) { if(dem==0) return; int currentV = Q[front]; front++; int nextTrai = currentV - 1; int nextPhai = currentV + 1; if(nextTrai > 0 && checkBFS[nextTrai] ==0) { if(check[nextTrai] == 0) { check[nextTrai] = vt; dem--; } checkBFS[nextTrai] = 1; Q[rear] = nextTrai; rear++; } if(dem == 0) return; if(nextPhai <= N && checkBFS[nextPhai] ==0) { if(check[nextPhai] == 0) { check[nextPhai] = vt; dem--; } checkBFS[nextPhai] = 1; Q[rear] = nextPhai; rear++; } if(dem==0) return; } } void BFS_phai(int vt, int dem) { for(int i=0;i<=N;i++) checkBFS[i] = 0; front = rear = 0; Q[rear] = vt; checkBFS[vt] = 1; rear++; if(check[vt] == 0) { check[vt] = vt; dem--; } while (front<rear) { if(dem==0) return; int currentV = Q[front]; front++; int nextTrai = currentV - 1; int nextPhai = currentV + 1; if(nextPhai <= N && checkBFS[nextPhai]==0) { if(check[nextPhai] == 0) { check[nextPhai] = vt; dem--; } checkBFS[nextPhai]= 1; Q[rear] = nextPhai; rear++; } if(dem == 0) return; if(nextTrai > 0 && checkBFS[nextTrai]==0) { if(check[nextTrai] == 0) { check[nextTrai] = vt; dem--; } checkBFS[nextTrai]= 1; Q[rear] = nextTrai; rear++; } if(dem == 0) return; } } int tinh_KC(int check[]) { int sum = 0; for(int i=1;i<=N;i++) { if(check[i] == Door[1].P) sum += Door1[i]; else if(check[i] == Door[2].P) sum += Door2[i]; else if(check[i] == Door[3].P) sum+= Door3[i]; } return sum; } void Try(int k, int P1, int C1, int P2, int C2, int P3, int C3) { for(int i=0;i<=1;i++) { A[k] = i; if(k==3) { if(A[1] == 0) BFS_trai(P1,C1); else BFS_phai(P1,C1); if(A[2] == 0) BFS_trai(P2,C2); else BFS_phai(P2,C2); if(A[3] == 0) BFS_trai(P3,C3); else BFS_phai(P3,C3); int sum = tinh_KC(check); if(sum<Min) Min = sum; for(int i=1;i<=N;i++) check[i] = 0; } else Try(k+1,P1,C1,P2,C2,P3,C3); } } int main() { freopen("input.txt","r",stdin); int tc; cin>>tc; for(int tci=1;tci<=tc;tci++) { cin>>N; for(int i=1;i<=3;i++) { cin>>Door[i].P>>Door[i].C; } Create(); //BFS_trai(6,2); //BFS_trai(4,5); for(int i=1;i<=N;i++) check[i] = 0; Min = 999999; //1 2 3 Try(1,Door[1].P,Door[1].C,Door[2].P,Door[2].C,Door[3].P,Door[3].C); // 1 3 2 Try(1,Door[1].P,Door[1].C,Door[3].P,Door[3].C,Door[2].P,Door[2].C); // 2 1 3 Try(1,Door[2].P,Door[2].C,Door[1].P,Door[1].C,Door[3].P,Door[3].C); // 2 3 1 Try(1,Door[2].P,Door[2].C,Door[3].P,Door[3].C,Door[1].P,Door[1].C); // 3 1 2 Try(1,Door[3].P,Door[3].C,Door[1].P,Door[1].C,Door[2].P,Door[2].C); // 3 2 1 Try(1,Door[3].P,Door[3].C,Door[2].P,Door[2].C,Door[1].P,Door[1].C); cout<<"Case #"<<tci<<endl<<Min<<endl; } } Hugo_Bandau #include <iostream> using namespace std; int N,M,rH,cH,pH; int MaTranKe[100][100]; int check[100][100]; int Q[50000]; int front, rear; int kq; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; bool checkTren(int rowC,int colC, int rowN, int colN) { if(MaTranKe[rowN][colN] == 0 || MaTranKe[rowC][colC] == 3 || MaTranKe[rowC][colC] == 5 || MaTranKe[rowC][colC] == 6) return false; if(MaTranKe[rowN][colN] == 1 || MaTranKe[rowN][colN] == 2 || MaTranKe[rowN][colN] == 5 || MaTranKe[rowN][colN] == 6) return true; else return false; } bool checkDuoi(int rowC,int colC, int rowN, int colN) { if(MaTranKe[rowN][colN] == 0 || MaTranKe[rowC][colC] == 3 || MaTranKe[rowC][colC] == 4 || MaTranKe[rowC][colC] == 7) return false; if(MaTranKe[rowN][colN] == 1 || MaTranKe[rowN][colN] == 2 || MaTranKe[rowN][colN] == 4 || MaTranKe[rowN][colN] == 7) return true; else return false; } bool checkTrai(int rowC,int colC, int rowN, int colN) { if(MaTranKe[rowN][colN] == 0 || MaTranKe[rowC][colC] == 2 || MaTranKe[rowC][colC] == 4 || MaTranKe[rowC][colC] == 5) return false; if(MaTranKe[rowN][colN] == 1 || MaTranKe[rowN][colN] == 3 || MaTranKe[rowN][colN] == 4 || MaTranKe[rowN][colN] == 5) return true; else return false; } bool checkPhai(int rowC,int colC, int rowN, int colN) { if(MaTranKe[rowN][colN] == 0 || MaTranKe[rowC][colC] == 2 || MaTranKe[rowC][colC] == 6 || MaTranKe[rowC][colC] == 7) return false; if(MaTranKe[rowN][colN] == 1 || MaTranKe[rowN][colN] == 3 || MaTranKe[rowN][colN] == 6 || MaTranKe[rowN][colN] == 7) return true; else return false; } void BFS(int vt) { front = rear = 0; int r = vt/M; int c = vt%M; check[r][c] = 1; Q[rear] = vt; rear++; while (front<rear) { int currentV = Q[front]; front++; int row = currentV/M; int col = currentV%M; for(int i=0;i<4;i++) { int x = row + dx[i]; int y = col + dy[i]; if(x<0 || x>=N || y<0 || y>=M) continue; else { if(i==0) { if(check[x][y] == 0 && checkTren(row,col,x,y)) { check[x][y] = check[row][col] + 1; Q[rear] = x*M + y; rear++; if(check[x][y] <=pH) kq++; } } else if(i==1) { if(check[x][y] == 0 && checkDuoi(row,col,x,y)) { check[x][y] = check[row][col] + 1; Q[rear] = x*M + y; rear++; if(check[x][y] <=pH) kq++; } } else if(i==2) { if(check[x][y] == 0 && checkTrai(row,col,x,y)) { check[x][y] = check[row][col] + 1; Q[rear] = x*M + y; rear++; if(check[x][y] <=pH) kq++; } } else { if(check[x][y] == 0 && checkPhai(row,col,x,y)) { check[x][y] = check[row][col] + 1; Q[rear] = x*M + y; rear++; if(check[x][y] <=pH) kq++; } } } } } } int main() { freopen("input.txt","r",stdin); int tc; cin>>tc; for(int tci=1;tci<=tc;tci++) { cin>>N>>M>>rH>>cH>>pH; for(int i=0;i<N;i++) for(int j=0;j<M;j++) { cin>>MaTranKe[i][j]; check[i][j] = 0; } kq = 1; BFS(rH*M+cH); /*for(int i=0;i<N;i++) for(int j=0;j<M;j++) { if(check[i][j]>0 && check[i][j]<=pH) kq++; }*/ cout<<"Case #"<<tci<<endl; cout<<kq<<endl; } }
Editor is loading...