code nuoc bien, domino, quan tuong, con voi
unknown
plain_text
2 years ago
5.8 kB
11
Indexable
#include <iostream> using namespace std; int map[105][105]; int vis[105][105]; int N,M; int dx[4] = {-1,0,1,0}; int dy[4] = {0,1,0,-1}; void DFS_water(int r, int c, int water){ vis[r][c] = 1; for (int k = 0; k < 4; k++) { int x = r + dx[k]; int y = c + dy[k]; if (x <0 || x >= N || y<0 ||y >=M || vis[x][y] !=0) continue; if (map[x][y] <= water) { vis[x][y] = 1; DFS_water(x,y,water); } } } void DFS_island(int r, int c) { vis[r][c] =1; for (int k = 0; k < 4; k++) { int x = r + dx[k]; int y = c + dy[k]; if (x <0 || x >= N || y<0 ||y >=M || vis[x][y] !=0) continue; DFS_island(x,y); } } void clear_vis(){ for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { vis[i][j] = 0; } } } int main(){ freopen("input.txt","r",stdin); cin>>N>>M; int tc =0; while (N!=0 && M!=0) { tc++; int low = 1000, high = -1; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin>>map[i][j]; if(map[i][j] < low) low = map[i][j]; if(map[i][j] > high) high = map[i][j]; } } int ans =-1; for (int water = low; water <= high; water++) { clear_vis(); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if ((i==0 || i == N-1 || j == 0 || j == M-1) && map[i][j] <= water) { if (vis[i][j] == 0) { DFS_water(i,j,water); } } } } int dem =0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (vis[i][j] ==0) { DFS_island(i,j); dem++; } } } if (dem > 1) { ans = water; break; } } if (ans == -1) { cout<<"Case "<<tc<<": Island never splits."<<endl; } else { cout<<"Case "<<tc<<": Island splits when ocean rises "<<ans<<" feet."<<endl; } cin>>N>>M; } return 0; } Domino // cach cua Minh #include <iostream> using namespace std; int map[7][8]; int vis_domino[7][7]; int vis_map[7][8]; int ans; int dx[2] = {0,1}; int dy[2] = {1,0}; void backTrack(int k){ if (k == 56) { ans++; return; } int r = k/8; int c = k%8; if (vis_map[r][c] == 1) { backTrack(k+1); } else { for (int t = 0; t < 2; t++) { int rr = r + dx[t]; int cc = c + dy[t]; if (rr >= 7 || cc>= 8 || vis_map[rr][cc] == 1) { continue; } if (vis_domino[map[r][c]][map[rr][cc]] == 0 || vis_domino[map[rr][cc]][map[r][c]] == 0) { vis_domino[map[r][c]][map[rr][cc]] = 1; vis_domino[map[rr][cc]][map[r][c]] = 1; vis_map[r][c] = vis_map[rr][cc] = 1; backTrack(k+1); vis_domino[map[r][c]][map[rr][cc]] = 0; vis_domino[map[rr][cc]][map[r][c]] = 0; vis_map[r][c] = vis_map[rr][cc] = 0; } } } } int main(){ freopen("input.txt","r",stdin); int T; cin>>T; for (int tc = 1; tc <= T; tc++) { for (int i = 0; i < 7; i++) { for (int j = 0; j < 8; j++) { cin>>map[i][j]; } } ans =0; backTrack(0); cout<<"Case #"<<tc<<endl<<ans<<endl; } return 0; } Quan tuong #include <iostream> using namespace std; //int map[205][205]; int vis[205][205]; int N,m,p,q,s,t; int pos[205][2]; int Qx[1000000]; int Qy[1000000]; int top, bot; bool is_Empty(){ return top == bot; } void push(int x, int y){ top++; Qx[top] = x; Qy[top] = y; } void pop(){ bot++; } void reset(){ top = bot = -1; } void clear(){ for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { //map[i][j] = 0; vis[i][j] = -1; } } } int dx[4] = {-1,-1,1,1}; int dy[4] = {-1,1,1,-1}; void BFS(){ push(p,q); vis[p][q] = 0; while (!is_Empty()) { int x = Qx[bot+1]; int y = Qy[bot+1]; pop(); for (int k = 0; k < 4; k++) { int xx = x; int yy = y; while (true) { xx += dx[k]; yy += dy[k]; if(xx<1||xx>N||yy<1||yy>N || vis[xx][yy] == -2){ break; } else if (vis[xx][yy] > vis[x][y] +1 || vis[xx][yy] == -1) { vis[xx][yy] = vis[x][y] +1; push(xx,yy); } } } } } int main(){ freopen("input.txt","r",stdin); int T; cin>>T; for (int tc = 1; tc <= T; tc++) { cin>>N>>m>>p>>q>>s>>t; //reset reset(); clear(); for (int i = 1; i <= m; i++) { cin>>pos[i][0]>>pos[i][1]; vis[pos[i][0]][pos[i][1]] = -2; } BFS(); cout<<vis[s][t]<<endl; } return 0; } Con voi #include <iostream> using namespace std; int N,K,M; int R[20]; int ans; bool check(){ bool q = true; for (int i = 0; i <= N-K; i++) { int r_max = 0; int count = 0; for (int j = i; j <= i + K-1; j++) { if (R[j] > r_max) { r_max = R[j]; count = 1; } else if (R[j] == r_max) { count++; } } if (count >= M) { q = false; break; } } return q; } void backTrack(int x, int sum){ if (sum > ans) { return; } if (check()) { if(sum< ans) ans = sum; return; } if (x == N) { return; } for (int i = 0; i < 2; i++) { if (i == 0) { backTrack(x+1,sum); } if (i == 1) { R[x]++; backTrack(x+1, sum+1); R[x]--; } } } int main(){ freopen("input.txt","r",stdin); int T; cin>>T; for (int tc = 1; tc <= T; tc++) { cin>>N>>K>>M; for (int i = 0; i < N; i++) { cin>>R[i]; } if (M != 1) { ans = 10000; backTrack(0,0); if(ans != 10000) cout<<"#"<<tc<<" "<<ans<<endl; else cout<<"#"<<tc<<" "<<-1<<endl; } else { cout<<"#"<<tc<<" "<<-1<<endl; } } return 0; }
Editor is loading...