Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
算法很苕,来回各扫描一次OK,O(N3)级的都可以16ms,但是WA了好几次,给大家提供一些需要注意的地方。0,下标一定不要打错(尤其是打重了!像for(int i = 1; i < N; i++{for(int i = 1; i < M; i++){...}}这种!因为这个WA了两次!) 1,一定要考慮T=1的情况!因为这个时猴来回的扫描都不存在!要单独判断解数! #include <iostream> #include <stdio.h> using namespace std; bool state[110][110][110]; int main() { int W, H, T; int cnt = 0; while(1){ scanf("%d%d%d", &W, &H, &T); if(W == 0 && H == 0 && T == 0) return W+H+T; printf("Robbery #%d:\n", cnt+1); cnt++; for(int k = 1; k <= T; k++){ for(int i = 1; i <= W; i++){ for(int j = 1; j <= H; j++){ state[k][i][j] = true; } } } int mes; scanf("%d", &mes); for(int ii = 0; ii < mes; ii++){ int t, x1, y1, x2, y2; scanf("%d%d%d%d%d", &t, &x1, &y1, &x2, &y2); for(int i = x1; i <= x2; i++){ for(int j = y1; j <= y2; j++){ state[t][i][j] = false; } } } bool youjie = true; int stateX[110], stateY[110]; bool weiyi[110] = {false}; int wygs = 0; int CNT = 0; int II, JJ; for(int i = 1; i <= W; i++){ for(int j = 1; j <= H; j++){ if(state[1][i][j]){ CNT ++; if(CNT == 1){ II = i; JJ = j; } //youjie = false; break; } } } if(CNT == 0) { youjie = false; goto meiyoujie; } if(T == 1){ if(CNT > 1){ printf("Nothing known.\n\n"); //continue; } else{ printf("Time step 1: The robber has been at %d,%d.\n\n", II, JJ); } continue; } for(int t = 2; t <= T; t++){ int cnt = 0; int I, J; for(int i = 1; i <= W; i++){ for(int j = 1; j <= H; j++){ if(!state[t][i][j]) continue; if(state[t-1][i][j] || (i>1 && state[t-1][i-1][j]) || (i<W && state[t-1][i+1][j]) || (j>1 && state[t-1][i][j-1]) || (j<H && state[t-1][i][j+1])){ cnt++; if(cnt == 1){ I = i; J = j; } } else{ state[t][i][j] = false; } } } if(cnt == 0){ youjie = false; break; } if(t == T && cnt == 1){ weiyi[T] = true; stateX[T] = I; stateY[T] = J; wygs ++; } } meiyoujie: if(!youjie){ printf("The robber has escaped.\n\n"); continue; } for(int t = T-1; t >= 1; t--){ int cnt = 0; int I, J; for(int i = 1; i <= W; i++){ for(int j = 1; j <= H; j++){ if(!state[t][i][j]) continue; if(state[t+1][i][j] || (i>1 && state[t+1][i-1][j]) || (i<W && state[t+1][i+1][j]) || (j>1 && state[t+1][i][j-1]) || (j<H && state[t+1][i][j+1])){ cnt ++; if(cnt == 1){ I = i; J = j; } } else{ state[t][i][j] = false; } } } if(cnt == 1){ wygs ++; weiyi[t] = true; stateX[t] = I; stateY[t] = J; } if(cnt == 0){ youjie = false; goto meiyoujie; } } if(wygs == 0){ printf("Nothing known.\n\n"); } else{ for(int t = 1; t <= T; t ++){ if(!weiyi[t]) continue; printf("Time step %d: The robber has been at %d,%d.\n", t, stateX[t], stateY[t]); } printf("\n"); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator