Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<stdlib.h>
- #include<iostream>
- #include<list>
- #include<set>
- #include<vector>
- #include<string>
- #include<math.h>
- #include <algorithm>
- using namespace std;
- class Position {
- public:
- int x;
- int y;
- Position(int x,int y) {
- this->x = x;
- this->y = y;
- }
- int distance(Position other) const {
- return this->distance(other.x,other.y);
- }
- int distance(int x, int y) const {
- return abs(this->x - x) + abs(this->y - y);
- }
- /*bool operator== (Position other) const {
- if (other.x == this->x && other.y == this->y) {
- return true;
- }
- return false;
- }*/
- bool operator< (Position other) const {
- return other.x - x + 100*(other.y - y);
- }
- /*~Position() {
- cout << "D" << x << y;
- }*/
- };
- class Cluster {
- public:
- set<Position> c;
- void merge(Cluster other) {
- cout << "\nTO MERGE:\n";
- cout << *this;
- cout << other;
- this->c.insert(other.c.begin(),other.c.end());
- cout << "MERGED: " << this << *this << "\n\n";
- }
- void add(Position p) {
- c.insert(p);
- }
- int distance(Cluster other) {
- int min = 10000;
- for (set<Position>::iterator pos = c.begin(); pos != c.end(); ++pos) {
- Position p = *pos;
- int distance = other.distance(p);
- if (min == -1 || min > distance) {
- min = distance;
- }
- }
- return min;
- }
- int distance(Position other) {
- return this->distance(other.x,other.y);
- }
- int distance(int x, int y) {
- int min = 10000;
- for (set<Position>::iterator pos = c.begin(); pos != c.end(); ++pos) {
- Position p = *pos;
- if (min == -1 || min > p.distance(x,y)) {
- min = p.distance(x,y);
- }
- }
- return min;
- }
- int size() {
- return this->c.size();
- }
- operator const char* () const {
- string output = "";
- char* buffer = (char*) calloc (50,sizeof(char));
- sprintf(buffer,"Cluster of size %d: ",(int)this->c.size());
- output = output.append(buffer);
- for (set<Position>::iterator i = this->c.begin(); i!=this->c.end(); ++i) {
- Position pos = *i;
- sprintf(buffer,"[%d,%d], ",pos.x,pos.y);
- output = output.append(buffer);
- }
- output = output.append("\n");
- return output.c_str();
- }
- };
- enum Direction {
- UP,
- DOWN,
- LEFT,
- RIGHT
- };
- class Move {
- public:
- Move(int x, int y, Direction direction) {
- this->x = x;
- this->y = y;
- this->direction = direction;
- }
- int x;
- int y;
- Direction direction;
- };
- typedef vector< vector<int> > Board;
- vector<Cluster> clusters(Board board, int color, int distance = 1) {
- vector<Cluster> clusters;
- for (int i=0; i < board.size(); i++) {
- for (int j=0; j < board[i].size(); j++) {
- if (board[i][j] == color) {
- vector<int> tested;
- for (int k=0; k<clusters.size(); k++) {
- Cluster cluster = clusters[k];
- if (cluster.distance(i,j) <= distance) {
- tested.push_back(k);
- }
- }
- Cluster newCluster;
- newCluster.add(Position(i,j));
- if (tested.size() > 0 ) {
- for (int k=0; k<tested.size(); k++) {
- int l = tested[k];
- Cluster m = clusters[l];
- newCluster.merge(m);
- }
- for (int k=tested.size()-1; k>=0; k--) {
- clusters.erase(clusters.begin()+tested[k]);
- }
- }
- cout << "NEW CLUSTER " << newCluster;
- clusters.push_back(newCluster);
- }
- list<int> test;
- }
- }
- return clusters;
- }
- vector<Cluster> processClusters(vector<Cluster> clusters, int distance=2, int desiredSize = 4) {
- vector<Cluster> desired;
- while (desired.size() == 0) {
- for (int i=0; i<clusters.size(); i++) {
- cout << clusters[i] << &clusters[i];
- }
- vector<Cluster> newClusters;
- for(int i=0; i<clusters.size(); i++) {
- vector<int> local;
- for(int j=0; j<newClusters.size(); j++) {
- if (clusters[i].distance(newClusters[j])<=distance) {
- local.push_back(j);
- }
- }
- if (local.size() > 0) {
- Cluster newCluster;
- newCluster.merge(clusters[i]);
- for (int j=0; j<local.size(); j++) {
- newCluster.merge(newClusters[local[j]]);
- }
- for (int j=local.size()-1; j>=0; j--) {
- newClusters.erase(newClusters.begin()+j);
- }
- newClusters.push_back(newCluster);
- } else {
- newClusters.push_back(clusters[i]);
- }
- }
- clusters = newClusters;
- for(int i=0; i<clusters.size(); i++) {
- //cout << clusters[i].size() << '\n';
- for (int k=0; k<clusters[i].c.size(); k++) {
- Position pos = *(clusters[i].c.begin());
- //cout << k << " " << pos.x << " " << pos.y << '\n';
- }
- if (clusters[i].size() >= desiredSize) {
- desired.push_back(clusters[i]);
- }
- }
- distance++;
- }
- cout << "DESIRED\n";
- for (int i=0; i<desired.size(); i++) {
- cout << desired[i] << &desired[i];
- }
- return desired;
- }
- /* Function declarations */
- long getNextColour(int colours);
- Move generate_move(int colors, Board board);
- int* playIt(int colours, Board board, long startSeed);
- long current_seed;
- int main() {
- /*
- Read integer colors.
- Read integer N.
- Read N strings board[0], board[1], ..., board[N-1].
- Read integer startSeed.
- Call playIt(colors, board, startSeed). Let ret be the return value.
- Print integers ret[0], ret[1], ..., ret[29999]. Flush standard output stream.
- */
- /*list<int> test;
- test.push_back(0);
- list<int>::iterator i;
- for(i=test.begin(); i != test.end(); ++i) cout << *i << " ";
- cout << endl;
- */
- int colors,N;
- long startSeed;
- Board board;
- if (false) {
- //cout << "Number of colours: ";
- cin >> colors;
- //cout << "Length of board-side: ";
- cin >> N;
- board.resize(N);
- for(int i=0; i < N; i++) {
- board[i].resize(N);
- for (int j=0; j<N; j++) {
- scanf("%1d",&board[i][j]);
- }
- }
- cin >> startSeed;
- } else {
- colors = 2;
- N = 3;
- board.resize(N);
- for(int i=0; i < N; i++) {
- board[i].resize(N);
- }
- board[0][0] = 0;
- board[0][1] = 1;
- board[0][2] = 1;
- board[1][0] = 0;
- board[1][1] = 1;
- board[1][2] = 0;
- board[2][0] = 0;
- board[2][1] = 0;
- board[2][2] = 1;
- startSeed = 1;
- }
- flush(cout);
- int *ret = playIt(colors, board, startSeed);
- for (int i=0; i<3; i++) {
- cout << ret[i] << '\n';
- }
- }
- long getNextColour(int colours) {
- long last_seed = current_seed;
- current_seed = (current_seed * 48271) % 2147483647;
- return last_seed % colours;
- }
- Move generate_move(int colors, Board board) {
- vector<Cluster> cs = clusters(board,1);
- Position p = *cs[0].c.begin();
- return Move(p.x,p.y,UP);
- }
- int* playIt(int colors, Board board, long startSeed) {
- int *moves = (int*) calloc (3,sizeof(int));
- // Setup
- current_seed = startSeed;
- for (int i = 0; i<1; i=i+3) {
- Move move = generate_move(colors, board);
- moves[i]= move.x;
- moves[i+1] = move.y;
- moves[i+2] = move.direction;
- }
- return moves;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement