Instantly share code, notes, and snippets.

# oldsnuke/gist:854387 Created Mar 4, 2011

SCOTLAND YARD
 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define error_X(n) {printf("POLICE WIN! (%s)\n",NUM_TO_ERROR_X[n]);return 0;} #define error_P(n) {printf("Mr.X WIN! (%s)\n",NUM_TO_ERROR_P[n]);return 0;} #define win_P {printf("POLICE WIN!!\n");return 0;} #define win_X {printf("Mr.X WIN!!\n");return 0;} #define MAX_MEM 1000000 using namespace std; const char NUM_TO_TICKET[4][20] = {"TAXI TICKET","BUS TICKET","UNDERGROUND TICKET","BLACK TICKET"}; const char NUM_TO_ERROR_X[11][50] = {"size of MEM is too big","size of X is small","size of X is not 5(Double Move)","X's parameter ERROR(Double Move)","wrong way(Double Move)","TICKET ERROR(Double Move)"," Double Move TICKET ERROR","X's parameter ERROR","wrong way","TICKET ERROR","Mr.X can move"}; const char NUM_TO_ERROR_P[7][50] = {"size of MEM is too big","size of P is not 10","P's parameter ERROR","wrong way","TICKET ERROR","POLICE's POS ERROR","POLICE can move"}; const int APPEAR_TURN[5] = {3,8,13,18,24}; /////////////////////////////// class Mr_X { public: vector Mr_X_AI (int N, int S, const vector WAY[4][200], const vector& START, int TURN, int X_POS, const int P_POS[5], const int X_TICKET[5], const int P_TICKET[5][3]){ vector X, X_list[2]; int rand_I, list_N = 0; bool CHECK; for(int j = 0; j < 3; j++) if(X_TICKET[j] > 0 || X_TICKET[3] > 0) for(int i = 0; i < WAY[j][X_POS].size(); i++){ CHECK = true; for(int h = 0; h < 5; h++) if(WAY[j][X_POS][i] == P_POS[h]) CHECK = false; if(CHECK){ X_list[0].push_back(WAY[j][X_POS][i]); if(X_TICKET[j] > 0) X_list[1].push_back(j); else X_list[1].push_back(3); list_N++; } } if(list_N){ rand_I = rand()%list_N; X.push_back(X_list[0][rand_I]); X.push_back(X_list[1][rand_I]); } else { X.push_back(-1); X.push_back(-1); } return X; } }; /////////////////////////////// /////////////////////////////// class POLICE { public: vector POLICE_AI (int N, int S, const vector WAY[4][200], const vector& START, int TURN, int X_POS, int X_USED_TICKET[25], const int P_POS[5], const int X_TICKET[5], const int P_TICKET[5][3]){ vector P, P_list[5][2]; int rand_I, list_N, POS_COPY[5]; bool CHECK; for(int i = 0; i < 5; i++) POS_COPY[i] = P_POS[i]; for(int k = 0 ; k < 5; k++){ list_N = 0; for(int j = 0; j < 3; j++) if(P_TICKET[k][j] > 0) for(int i = 0; i < WAY[j][P_POS[k]].size(); i++){ CHECK = true; for(int h = 0; h < 5; h++) if(WAY[j][P_POS[k]][i] == POS_COPY[h]) CHECK = false; if(CHECK) {P_list[k][0].push_back(WAY[j][P_POS[k]][i]); P_list[k][1].push_back(j); list_N++;} } if(list_N){ rand_I = rand()%list_N; P.push_back(P_list[k][0][rand_I]); P.push_back(P_list[k][1][rand_I]); POS_COPY[k] = P_list[k][0][rand_I]; } else { P.push_back(-1); P.push_back(-1); } } return P; } }; /////////////////////////////// bool load(int& N,int WAY_N[4],int& S,vector WAY[4][200],vector& START,int X_TICKET[5],int P_TICKET[5][3]){ FILE* fp; int x, y; fp = fopen("in","r"); if(fp == NULL){puts("File not found."); return false;} fscanf(fp,"%d",&N); for(int i = 0; i < 4; i++){ fscanf(fp,"%d",&WAY_N[i]); for(int j = 0; j < WAY_N[i]; j++){ fscanf(fp,"%d%d",&x,&y); WAY[i][x].push_back(y); WAY[i][y].push_back(x);} } fscanf(fp,"%d",&S); for(int i = 0; i < S; i++){ fscanf(fp,"%d",&x); START.push_back(x);} for(int i = 0; i < 5; i++) fscanf(fp,"%d",&X_TICKET[i]); for(int j = 0; j < 3; j++) fscanf(fp,"%d",&P_TICKET[0][j]); for(int i = 1; i < 5; i++) for(int j = 0; j < 3; j++) P_TICKET[i][j] = P_TICKET[0][j]; fclose(fp); return true; } void set_POS(int& X_POS, int P_POS[5], int S, vector START){ int RAN_POS; RAN_POS = rand() % S; X_POS = START[RAN_POS]; S--; START[RAN_POS] = START[S]; for(int i = 0; i < 5; i++){ RAN_POS = rand() % S; P_POS[i] = START[RAN_POS]; S--; START[RAN_POS] = START[S]; } return; } bool check_X_CAN(int X_POS, const int X_TICKET[5], const vector WAY[4][200]){ for(int k = 0; k < 3; k++){ if((X_TICKET[k] > 0 || X_TICKET[3] > 0) && WAY[k][X_POS].size() > 0) return true; } return false; } bool check_P_CAN(const int P_POS[5], const int P_TICKET[5][3], const vector WAY[4][200], int x){ bool CHECK; for(int k = 0; k < 3; k++){ if(P_TICKET[x][k] > 0){ for(int i = 0; i < WAY[k][P_POS[x]].size(); i++){ CHECK = true; for(int j = 0; j < 5; j++) if(WAY[k][P_POS[x]][i] == P_POS[j]) CHECK = false; if(CHECK) return true; } } } return false; } int main(){ srand( (unsigned)time( NULL ) ); Mr_X XC; POLICE PC; int N, WAY_N[4], S, TURN, X_POS, X_POS_FOR_P, P_POS[5], X_TICKET[5], P_TICKET[5][3], X_USED_TICKET[25]; vector WAY[4][200], START, X, P; bool CHECK; if(!load(N,WAY_N,S,WAY,START,X_TICKET,P_TICKET)) return 0; set_POS(X_POS,P_POS,S,START); printf("Mr.X is %d.\n", X_POS); for(int i = 0; i < 5; i++) printf("POLICE_%d is %d.\n", i, P_POS[i]); for(TURN = 1; TURN <= 24 - X_TICKET[4]; TURN++){ printf("TURN %d",TURN); for(int i = 0; i < 5; i++) if(TURN == APPEAR_TURN[i]) printf("(APPEAR TURN)"); puts(""); X_POS_FOR_P = 0; X = XC.Mr_X_AI(N, S, WAY, START, TURN, X_POS, P_POS, X_TICKET, P_TICKET); if(X.size() < 2) error_X(1); if(X[0] == -1 && X[1] == -1){ if(check_X_CAN(X_POS,X_TICKET,WAY)) error_X(10); X_USED_TICKET[TURN] = -1; puts("Mr.X CAN'T MOVE."); } else { if(X[0] == 0){ if(X.size() != 5) error_X(2); for(int j = 1; j < 4; j+=2) if(X[j] < 1 || X[j] > N || X[j+1] < 0 || X[j+1] > 3) error_X(3); for(int j = 1; j < 4; j+=2){ CHECK = true; if(X[1] == 3){ for(int k = 0; k < 4; k++) for(int i = 0; i < WAY[k][X_POS].size(); i++) if(WAY[k][X_POS][i] == X[j]) CHECK = false; } else { for(int i = 0; i < WAY[X[j+1]][X_POS].size(); i++) if(WAY[X[j+1]][X_POS][i] == X[j]) CHECK = false; } if(CHECK) error_X(4); X_POS = X[j]; X_TICKET[X[j+1]]--; X_USED_TICKET[TURN+j/2] = X[j+1]; if(X_TICKET[X[j+1]] < 0) error_X(5); for(int i = 0; i < 5; i++) if(APPEAR_TURN[i] == TURN+j/2) X_POS_FOR_P = X_POS; } X_TICKET[4]--; if(X_TICKET[4] < 0) error_X(6); puts("Double Move."); TURN++; for(int j = 1; j < 4; j+=2) printf("Mr.X go to %d. (Use %s)\n",X[j],NUM_TO_TICKET[X[j+1]]); } else { if(X.size() != 2 || X[0] < 1 || X[0] > N || X[1] < 0 || X[1] > 3) error_X(7); CHECK = true; if(X[1] == 3){ for(int k = 0; k < 4; k++) for(int i = 0; i < WAY[k][X_POS].size(); i++) if(WAY[k][X_POS][i] == X[0]) CHECK = false; } else { for(int i = 0; i < WAY[X[1]][X_POS].size(); i++) if(WAY[X[1]][X_POS][i] == X[0]) CHECK = false; } if(CHECK) error_X(8); X_POS = X[0]; X_TICKET[X[1]]--; X_USED_TICKET[TURN] = X[1]; if(X_TICKET[X[1]] < 0) error_X(9); printf("Mr.X go to %d. (Use %s)\n",X[0],NUM_TO_TICKET[X[1]]); for(int i = 0; i < 5; i++) if(APPEAR_TURN[i] == TURN) X_POS_FOR_P = X_POS; } } for(int i = 0; i < 5; i++) if(X_POS == P_POS[i]) win_P; P = PC.POLICE_AI(N, S, WAY, START, TURN, X_POS_FOR_P, X_USED_TICKET, P_POS, X_TICKET, P_TICKET); if(P.size() != 10) error_P(1); for(int j = 0; j < 10; j+=2){ if(P[j] == -1 && P[j+1] == -1){ if(check_P_CAN(P_POS,P_TICKET,WAY,j/2)) error_P(6); } else { if(P[j] < 1 || P[j] > N || P[j+1] < 0 || P[j+1] > 3) error_P(2); CHECK = true; for(int i = 0; i < WAY[P[j+1]][P_POS[j/2]].size(); i++) if(WAY[P[j+1]][P_POS[j/2]][i] == P[j]) CHECK = false; if(CHECK) error_P(3); P_POS[j/2] = P[j]; P_TICKET[j/2][P[j+1]]--; X_TICKET[P[j+1]]++; if(P_TICKET[j/2][P[j+1]] < 0) error_P(4); for(int i = 0; i < 5; i++) if(i != j/2 && P_POS[i] == P_POS[j/2]) error_P(5); } } for(int j = 0; j < 10; j+=2) if(P[j] == -1 && P[j+1] == -1) printf("POLICE_%d CAN'T MOVE.\n",j/2); else printf("POLICE_%d go to %d. (Use %s)\n",j/2,P[j],NUM_TO_TICKET[P[j+1]]); for(int i = 0; i < 5; i++) if(X_POS == P_POS[i]) win_P; } win_X; return 0; }