Untitled
unknown
plain_text
6 months ago
13 kB
2
Indexable
Never
Problem 1: Minimum Knight step from (x1,y1) to (x2,y2) #define _CRT_SECURE_NO_WARNINGS #include <iostream> using namespace std; int visit[1000][1000] = {0}; int Qx[1000001]; int Qy[1000001]; int Qd[1000001]; // save khoang cach tu start den diem visiting int f = -1; int r = -1; void Push(int x, int y, int d){ r++; Qx[r] = x; Qy[r] = y; Qd[r] = d; } void Pop(int &x,int &y, int&d){ f++; x = Qx[f]; y = Qy[f]; d = Qd[f]; } int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2 }; int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 }; bool isInside(int x, int y, int N, int M) { if (x >= 1 && x <= N && y >= 1 && y <= M) return true; return false; } int BFS(int start[2], int end[2], int n, int m, int d){ // push START Push(start[0],start[1],d); visit[start[0]][start[1]] = 1; // mark as visited the start while (r!=f) { Pop(start[0],start[1],d); // check lan can if (start[0] == end[0] && start[1] == end[1]) { return d; break; } int x1,y1; for (int i = 0; i < 8; i++) { x1 = start[0] + dx[i]; y1 = start[1] + dy[i]; if (isInside(x1,y1,n,m) && !visit[x1][y1]) { Push(x1,y1,d+1); visit[x1][y1] = 1; } } } return -1; } int main(){ int n,m; int T; cin>>T; freopen("input.txt","r",stdin); for (int tc = 1; tc <= T; tc++) { cin>>n>>m; //reset f = r = -1; for (int i = 0; i <= 1000; i++) { for (int j = 0; j <= 1000; j++) { visit[i][j] = 0; } } // INPUT int Start[2]; int End[2]; cin>>Start[0]>>Start[1]>>End[0]>>End[1]; cout<<"Case #"<<tc<<endl<<BFS(Start,End,n,m,0)<<endl; } return 0; } Bai 2: princess #include <stdio.h> #include <iostream> using namespace std; int ans; int visit[201][201]; int map[201][201]; int Qx[50000]; int Qy[50000]; int Qd[50000]; // save khoang cach tu start den diem visiting int f = -1; int r = -1; void Push(int x, int y, int d){ r++; Qx[r] = x; Qy[r] = y; Qd[r] = d; } void Pop(int &x,int &y, int&d){ f++; x = Qx[f]; y = Qy[f]; d = Qd[f]; } int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-1}; bool isInside(int x, int y, int N) { if (x >= 1 && x <= N && y >= 1 && y <= N) return true; return false; } int BFS1(int x,int y,int n, int d){ // push START Push(x,y,d); while (r!=f) { Pop(x,y,d); int x1,y1; for (int i = 0; i < 4; i++) { x1 = x + dx[i]; y1 = y + dy[i]; if (isInside(x1,y1,n) && !visit[x1][y1] && 1==map[x1][y1]) // { Push(x1,y1,d+1); visit[x1][y1] = 1; } if (isInside(x1,y1,n) && !visit[x1][y1] && 2==map[x1][y1]) // { visit[x1][y1] = 1; return d+1; } } } return -1; } int main(){ int n; int T; cin>>T; //freopen("input.txt","r",stdin); for (int tc = 1; tc <= T; tc++) { cin>>n; //reset f = r = -1; for (int i = 1; i <= 201; i++) { for (int j = 1; j <= 201; j++) { visit[i][j] = 0; map[i][j] = 0; } } // INPUT for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin>>map[i][j]; } } ans = 0; int d1 = BFS1(1,1,n,0); //reset Queue and Visit[] f = r = -1; for (int i = 0; i < 50000; i++) { Qx[i] = Qy[i] = Qd[i] = 0; } for (int i = 1; i <= 201; i++) { for (int j = 1; j <= 201; j++) { visit[i][j] = 0; } } ////////////// int d2 = BFS1(n,n,n,0); //////// if (-1 == d1 || -1 == d2) { ans = -1; }else { ans = d1 + d2; } cout<<ans<<endl; } return 0; } Bai 3: Find cycle Given a directed graph, check whether the graph contains a cycle or not #define _CRT_SECURE_NO_WARNINGS #include <iostream> using namespace std; int visit[1000]; int v, e; int Qx[100000]; int f = -1; int start[1000]; int dest[1000]; void Push(int x){ f++; Qx[f] = x; } void Pop(int &x){ x = Qx[f]; f--; } int BFS(int x){ Push(x); visit[x] = 1; while (-1!=f) { Pop(x); for (int i = 0; i < e; i++) { if (start[i]==x && !visit[dest[i]]) { visit[dest[i]] = 1; Push(dest[i]); break; } else if (start[i]==x && visit[dest[i]]) { return 1; } } } return 0; } int main(){ int T; cin>>T; //freopen("input.txt","r",stdin); for (int tc = 1; tc <= T; tc++) { cin>>v>>e; //reset f = -1; for (int i = 0; i <= 1000; i++) { start[i] = dest[i] = visit[i] = 0; } // INPUT for (int i = 0; i < e; i++) { cin>>start[i]>>dest[i]; } cout<<"Case #"<<tc<<endl; cout<<BFS(start[0])<<endl; } return 0; } Bài 4: Point of balances...điểm cân bằng lực từ #include<iostream> #include<stdio.h> using namespace std; double x[15]; double weight[15]; double Answer; int N; double BinarySearch(double left, double right){ double mid = (left + right) / 2; double F1 = 0; double F2 = 0; for(int i = 1; i<= N; i++){ if (x[i] < mid) F1 += weight[i]/( (mid - x[i]) * (mid - x[i]) ); if (x[i] > mid) F2 += weight[i]/( (x[i]-mid) * (x[i]-mid) ); } if ( F1 - F2 < 0.0000000001 && F1 - F2 > -0.0000000001) return mid; if ( F1 < F2) return BinarySearch(left,mid); if ( F1 > F2) return BinarySearch(mid,right); } int main(int argc, char** argv) { int test_case; int T; for(test_case = 1; test_case <= 10; ++test_case) { cin >> N; for( int i =1; i<= N; i++) cin >> x[i]; for( int i =1; i<= N; i++) cin >> weight[i]; printf("#%d",test_case); for( int i =1; i< N; i++){ Answer = BinarySearch(x[i], x[i+1]); // Print the answer to standard output(screen). printf(" %.10lf",Answer); } cout<<endl; } return 0;//Your program should return 0 on normal termination. } Bai 5 : village Làng mạc Cho bản đồ mạng lưới giao thông giữa các làng mạc. Một vùng được định nghĩa là một tập hợp các làng mà từ bất kỳ một làng nào trong vùng đều có thể đi đến một làng khác trong vùng. Hãy tính số vùng trong bản đồ, số làng cô lập (làng không có đường đi đến bất kỳ làng khác) và số con đường đóng vai trò là “Cầu” giữa hai vùng (nếu bỏ con đường này đi thì số lượng vùng tăng lên 1). Input Dòng đầu có một số T là số lượng test của file input. Mỗi test được bố cục như sau: dòng đầu là một số nguyên dương N (N <= 300) N là số làng, tiếp theo là một ma trân A[i, j] trong đó A[i][j] có giá trị bằng 1 là có đường đi từ làng i tới làng j và 0 nếu không có đường từ làng i tới làng j. Dữ liệu đảm bảo nếu có đường từ làng i tới làng j thì cũng sẽ có đường ngược lại. Output Với mỗi test, in ra sốvùng có trên bản đồ, số làng cô lập và số đường đóng vai trò là cầu. If not visited -> so vung +1 Tu input-> hàng nào toàn 00000-> ko connect any village -> alone village + 1 -> visited = true; For ½ map Tim map i j = 1 (path 2 village) delete map i j =0 -> dem lai so vung If new region – old region = 1 C2: bool bfs(i,j) -> nếu vẫn còn path i -> j có cầu++ Bridge + 1 Map I j =1 // tra lai connection /// txt //// path routing #include <stdio.h> #include <iostream> using namespace std; int S[1000]; int t = -1; void Push(int x){ S[++t] = x; } void Pop(int &x){ x = S[t]; t--; } //data int M[100][2]; bool DFS(int s){ Push(s); // take mark // bai nay k can // // tranverse while (t!=-1) { Pop(s); for (int i = 0; i < 2; i++) { // check lan can if (M[s][i] == 99) {return true;} if (M[s][i] != -1) { Push(M[s][i]); M[s][i] == -1; } } } return false; } int main() { int n; for (int tc = 1; tc <= 10; tc++) { //reset M[][] va Stack t = -1; for (int i = 0; i < 100; i++) { M[i][0] = M[i][1] = -1; } cin>>n>>n; int s; for (int i = 0; i < n; i++) { cin>>s; if (M[s][0] == -1) { cin>>M[s][0]; }else { cin>>M[s][1]; } } cout<<"#"<<tc<<" "<<DFS(0)<<endl; } return 0; } // from 2 to 3 theo line 0 #include <stdio.h> #include <iostream> #define MAX_STACK 10000 using namespace std; struct Point { int row; int col; Point (int r, int c){ row = r; col = c; } Point (){ row = 0; col = 0; } }; class Stack { Point A[MAX_STACK]; public: int top; Stack(); ~Stack(); bool isEmpty(); bool isFull(); void push(Point s); Point pop(); Point peak(); void reset(); private: }; Stack::Stack() { top = -1; } Stack::~Stack() { } bool Stack::isEmpty(){ return (top == -1); } bool Stack::isFull(){ return (top == MAX_STACK - 1); } void Stack::push(Point s){ if (isFull()) { //cout<<"Stack overflow"; } ++top; A[top] = s; } Point Stack::pop(){ --top; return A[top + 1]; } Point Stack::peak(){ return A[top]; } void Stack::reset(){ top = -1; } Stack mStack; char Map[100][100]; bool is_ok = false; int rowstep[] = {0,0,-1,1}; int colstep[] = {1,-1,0,0}; int main() { int n; for (int tc = 1; tc <= 10; tc++) { is_ok = false; cin>>n; for (int i = 0; i < 100; i++) { cin>>Map[i]; } mStack.reset(); for (int i = 0; i < 100; i++) { for (int j = 0; j < 100; j++) { if (Map[i][j] == '2') { mStack.push(Point(i,j)); } } } // solution while (!mStack.isEmpty() && !is_ok){ Point newPoint; Point temp = mStack.pop(); for (int i = 0; i < 4; i++) { newPoint = Point(temp.row + rowstep[i],temp.col + colstep[i]); if (Map[newPoint.row][newPoint.col] == '3') { is_ok = true; break; } if (Map[newPoint.row][newPoint.col] == '0') { mStack.push(newPoint); Map[newPoint.row][newPoint.col] = '1'; } } } if (is_ok) { cout<<"#"<<tc<<" "<<1<<endl; }else { cout<<"#"<<tc<<" "<<0<<endl; } } return 0; } //// contact c1: need to pop all queue to ensure time sync for (queue) pop c2: input dang point (value, number_step or time or length) // code #include <stdio.h> #include <iostream> using namespace std; int a[1000] = {-1}; int visit[100] = {0}; int ds[100] = {0}; int Qx[100000]; int Qd[100000]; // save khoang cach tu start den diem visiting int f = -1; int r = -1; void Push(int x, int d){ r++; Qx[r] = x; Qd[r] = d; } void Pop(int &x, int&d){ f++; x = Qx[f]; d = Qd[f]; } void BFS(int x, int d, int n){ // push START Push(x,d); visit[x] = 1; // mark as visited the start while (r!=f) { Pop(x,d); // check lan can for (int i = 1; i <= n; i+=2) { if (a[i] == x && 1 != visit[a[i+1]] ) { Push(a[i+1],d+1); visit[a[i+1]] = 1; ds[a[i+1]] = d+1; } } } } int main(){ int n,start; int ans = 0; int d=0; int maxFreq = 0; //freopen("input.txt","r",stdin); for (int tc = 1; tc <= 10; tc++) { cin>>n>>start; //reset f = r = -1; for (int i = 0; i < 100; i++) { visit[i] = 0; ds[i] = 0; } // INPUT for (int i = 1; i <= n; i++) { cin>>a[i]; } // algorithm BFS(start,d,n); maxFreq = ds[0]; for (int i = 1; i < 100; i++) { maxFreq = max(maxFreq,ds[i]); } // tim value of maxFreq --> duyet nguoc for (int i = 99; i >= 1; i--) { if (ds[i] == maxFreq) { ans = i; break; } } cout<<"#"<<tc<<" "<<ans<<endl; } return 0; } // in so thuc 10 chu so sau dau phay //C++ cout.setf(ios::fixed); cout.setf(ios::showpoint); cout.precision(10); // C double x; printf("%0.10lf",x); return 0; // farmcover #include<iostream> using namespace std; const int MAX = 710; int N,M; int n_Hill; int Map[MAX][MAX]; bool visited[MAX][MAX]; bool tallest; int dx[8] = {-1,-1,-1, 0,0, 1,1,1}; int dy[8] = {-1, 0, 1,-1,1,-1,0,1}; void DFS(int row, int col) { visited[row][col] = true; for(int i = 0; i < 8; i++) { int r_next = row + dx[i]; int c_next = col + dy[i]; if(r_next >= 0 && r_next < N && c_next >= 0 && c_next < M) { // higher than current pos -> false if(tallest && Map[r_next][c_next] > Map[row][col]) tallest = false; // travese all same height pos if(Map[r_next][c_next] == Map[row][col] && !visited[r_next][c_next]) DFS(r_next, c_next); } } } int main() { int T; cin >> T; for(int test_case = 1; test_case <= T; ++test_case) { n_Hill = 0; cin >> N >> M; for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) { cin >> Map[i][j]; visited[i][j] = false; } for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) if(!visited[i][j]) { tallest = true; DFS(i, j); if(tallest) n_Hill++; } cout <<"#"<<test_case<<" " << n_Hill << endl; } return 0; }