Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

算法很苕,来回各扫描一次OK,O(N3)级的都可以16ms,但是WA了好几次,给大家提供一些需要注意的地方。

Posted by KatrineYang at 2016-07-26 23:03:28 on Problem 1104
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator