| ||||||||||
| 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