mayan game

mayan.cpp

/*
 * =====================================================================================
 *
 *       Filename:  mayan.cpp
 *
 *    Description:  mayan game
 *
 *        Version:  1.0
 *        Created:  2012年10月07日 00時15分49秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (), 
 *   Organization:  
 *
 * =====================================================================================
 */
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define MAX_HEIGHT 7
#define MAX_WIDTH 5

void swap(int *a, int *b) {
    int tmp = *a; 
    *a = *b; 
    *b = tmp; 
}

class Map {
private:
    short merged[MAX_HEIGHT][MAX_WIDTH]; // record the point at (x, y) whether sould be merged 
    // 0 - none
    // 1 - up/down
    // 2 - left/right
    // 3 - up/down/left/right

    bool _merge(); 
    bool scan(int x, int y);
    void slideDown(bool merge); 
public:
    int map[MAX_HEIGHT][MAX_WIDTH]; 
    
    Map(); 
    void copy_from(Map m); 
    void show(); 
    void merge(); 
    bool finished(); 
    bool same(Map m); 
    int move(int x, int y, int direction); 
}; 

Map::Map() {
    memset(this->map, 0, sizeof(this->map)); 
}

void Map::copy_from(Map m) {
    /*
     * Copy map data from other object
     */
    memcpy(this->map, m.map, sizeof(m.map)); 
}

void Map::show() {
    /*
     * Output the map of this object
     */
    printf("-----------\n"); 
    for(int i = 0; i < MAX_HEIGHT; i++) {
        for(int j = 0; j < MAX_WIDTH; j++) {
            printf("%d ", this->map[i][j]); 
        }
        printf("\n"); 
    }
}

bool Map::scan(int x, int y) {
    /*
     * Check if the point at (x, y) could be merged
     *
     * Return Value:
     * true - Merged
     * false - Unchange
     */
    int i = 1; 
    bool flag = false; 
    // right
    while(true) {
        if((y - i >= 0 && y - i < MAX_WIDTH)
           && this->map[x][y - i] == this->map[x][y]) {
            if(this->merged[x][y - i] == 1) {
                while(i--) {
                    this->merged[x][y - i] = 1; 
                }
                flag = true; 
                break; 
            }
            i++; 
        }else{
            if(i > 2) {
                while(i--) {
                    this->merged[x][y - i] = 1; 
                }
                flag = true; 
            }
            break; 
        }
    }
    i = 1;
    // left
    while(true) {
        if((y + i >= 0 && y + i < MAX_WIDTH) 
           && this->map[x][y + i] == this->map[x][y]) {
            if(this->merged[x][y + i] == 1) {
                while(i--) {
                    this->merged[x][y + i] = 1; 
                }
                flag = true; 
                break; 
            }
            i++; 
        }else{
            if(i > 2) {
                while(i--) {
                    this->merged[x][y + i] = 1; 
                }
                flag = true; 
            }
            break; 
        }
    }
    i = 1; 
    // up 
    while(true) {
        if((x + i >= 0 && x + i < MAX_HEIGHT)
           && this->map[x + i][y] == this->map[x][y]) {
            if(this->merged[x + i][y] == 2) {
                while(i--) {
                    this->merged[x + i][y] = 2; 
                }
                flag = true; 
                break; 
            }
            i++; 
        }else{
            if(i > 2) {
                while(i--) {
                    this->merged[x + i][y] = 2; 
                }
                flag = true;
            }
            break; 
        }
    }
    i = 1; 
    // down
    while(true) {
        if((x - i >= 0 && x - i < MAX_HEIGHT)
           && this->map[x - i][y] == this->map[x][y]) {
            if(this->merged[x - i][y] == 2) {
                while(i--) {
                    this->merged[x - i][y] = 2; 
                }
                flag = true; 
                break; 
            }
            i++; 
        }else{
            if(i > 2) {
                while(i--) {
                    this->merged[x - i][y] = 2; 
                }
                flag = true; 
            }
            break; 
        }
    }
    return flag; 
}

bool Map::_merge() {
    /*
     * Single merge step
     */
    bool flag = false; 
    bool re = false; 
    bool blank_line; 
    memset(this->merged, 0, sizeof(this->merged)); 
    for(int i = 0; i < MAX_HEIGHT; i++) {
        blank_line = true; 
        for(int j = 0; j < MAX_WIDTH; j++) {
            if(this->map[i][j]) {
                re = this->scan(i, j); 
                if(!flag && re) {
                    flag = true; 
                    re = false; 
                }
                blank_line = false; 
            }
        }
        if(blank_line) {
            break; 
        }
    }
    return flag; 
} 
 
void Map::merge() {
    /*
     * Merge the map
     */
    bool re = this->_merge(); 
    while(re) {
        this->slideDown(true); 
        re = this->_merge(); 
    }
}

void Map::slideDown(bool merge) {
    if(merge) {
        for(int i = 0; i < MAX_HEIGHT; i++) {
            for(int j = 0; j < MAX_WIDTH; j++) {
                if(this->merged[i][j]) {
                    this->map[i][j] = 0; 
                }
            }
        }
    }
    int k = 0; 
    for(int i = 0; i < MAX_WIDTH; i++) {
        k = 0; 
        for(int j = 0; j < MAX_HEIGHT; j++) {
            if(this->map[j][i]) {
                this->map[k++][i] = this->map[j][i]; 
            }
        }
        k = k; 
        for(; k < MAX_HEIGHT; k++) {
            this->map[k][i] = 0; 
        }
    }
}

int Map::move(int x, int y, int direction) {
    /*
     * Move a box
     *
     * Return Value:
     *
     * 0 - Move Success
     * -1 - Move Failed
     */
    if(x + direction >= 0 && x + direction < MAX_WIDTH) {
        if(this->map[y][x] == this->map[y][x+direction]) {
            return -1; 
        }
        int tmp; 
        tmp = this->map[y][x]; 
        this->map[y][x] = this->map[y][x + direction]; 
        this->map[y][x + direction] = tmp; 
        this->slideDown(false); 
        return 0; 
    }
    return -1; 
}

bool Map::finished() {
    for(int i = 0; i < MAX_HEIGHT; i++) {
        for(int j = 0; j < MAX_WIDTH; j++) {
            if(this->map[i][j]) {
                return false; 
            }
        }
    }
    return true; 
}

bool Map::same(Map b) {
    for(int i = 0; i < MAX_HEIGHT; i++) {
        for(int j = 0; j < MAX_WIDTH; j++) {
            if(this->map[i][j] != b.map[i][j]) {
                return false; 
            }
        }
    }
    return true;
}

int n; 
bool solved = false; 
Map start; 

typedef struct {
    int x, y, direction; 
} Plan; 

Plan plans[6]; 

void search(int step, Map now) {
    if(now.finished()) {
        if(step == n) {
            solved = true; 
            return; 
        }
        return; 
    }
    if(step == n) {
        return; 
    }
    Map tmp; 
    int re = 0; 
    tmp.copy_from(now); 
    for(int j = 0; j < MAX_WIDTH; j++) {
        for(int i = 0; i < MAX_HEIGHT; i++) {
            if(now.map[i][j]) {
                // left
                re = now.move(j, i, 1); 
                if(re != -1) {
                    now.merge(); 
                    plans[step] = {j, i, 1}; 
                    search(step + 1, now); 
                    if(solved) {
                        return; 
                    }
                    plans[step] = {0, 0, 0}; 
                }
                now.copy_from(tmp); 
                // right
                re = now.move(j, i, -1); 
                if(re != -1) {
                    now.merge(); 
                    plans[step] = {j, i, -1}; 
                    search(step + 1, now); 
                    if(solved) {
                        return; 
                    }
                    plans[step] = {0, 0, 0}; 
                }
                now.copy_from(tmp); 
            }
        }
    }
}

int main() {
    FILE *fin = fopen("mayan.in", "r"); 
    FILE *fout = fopen("mayan.out", "w"); 
    fscanf(fin, "%d", &n); 
    int a; 
    for(int i = 0; i <= MAX_WIDTH; i++) {
        int j = 0;  
        while(1) {
            fscanf(fin, "%d", &a); 
            if(a == 0) {
                break; 
            }
            start.map[j++][i] = a; 
        }
    }
//    start.show(); 
//    start.move(1, 0, 1); 
//    start.merge(); 
//    start.show(); 
//    start.move(0, 0, 1); 
//    start.merge(); 
//    start.show(); 
//    start.move(2, 2, 1); 
//    start.merge(); 
//    start.show(); 
//    start.move(1, 1, 1); 
//    start.merge(); 
//    start.show(); 
//    start.move(3, 0, 1); 
//    start.merge(); 
//    start.show(); 
    search(0, start); 
    if(solved) {
        for(int i = 0; i < n; i++) {
            fprintf(fout, "%d %d %d\n", plans[i].x, plans[i].y, plans[i].direction); 
        }
        return 0; 
    }
    fprintf(fout, "-1\n"); 
    return 0; 
}