ACM-ZOJ 1008 DFS 一路好题

ACM-ZOJ 1008 DFS 一道好题

     个人将题目理解为有n*n张卡片操作就像题目那样，也没有出现超时，可能这也不是很暴力吧，但是还是运行了将近6s，不知道排第一的用java写出0ms的和其他用c++写在30ms的是怎么写的。同时最开始我用3维数组存储，好理解但是貌似不是很好写于是还是用的二维，第一维是各个卡片，第二维是没张卡片的上下左右的数。

    还有不好理解的就是这深搜的是是否能按题意排列出正确的序列(图样）。

//2012-10-10 17:04:26	 Accepted	1008	C++	5760ms	188kb
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAX(36);
int map[MAX][4];  //存卡片
int numOfCard[MAX]; //每种卡片的数量
int _right[MAX];//卡片的正确排序
int diff;  //现在有几种不同的卡片
int n;

bool DFS(int pos) {
    if (pos == n*n)  return true;
    int i(0);
    for ( i = 0; i != diff; ++i) {//i相当于不同种卡片的序号
        if (numOfCard[i] == 0)  continue; //这种卡片用完了
        //如果有前一列，pos%n （0，n，2n，3n...是第一列，除了第一列都有前一列）
        //前一排的右值!=现在的左值
        if (pos%n != 0 && map[ _right[pos - 1] ][1] != map[i][3])  continue; //换卡

        //如果有前一行，pos/n （0到n-1是第一行，除了第一行都有前一行）
        //前一行的下值!=现在的上值
        if (pos/n != 0 && map[ _right[pos - n] ][2] != map[i][0])  continue; //换卡

        _right[pos] = i; //这个位置应该填该种卡片  
        --numOfCard[i];

        if (DFS(pos + 1))  return true;
        else ++numOfCard[i];    //DFS返回false后执行恢复现场

    }
    return false;
}


int main() {
    int game(1);  //进行游戏的次数
    while ( scanf("%d", &n) , n) {
        memset(map, 0, sizeof(map));
        memset(numOfCard, 0, sizeof(numOfCard));
        memset(_right, 0, sizeof(_right));
        diff = 0;
        int i(0), j(0);
        int up, down, left, _right;

        //input
        for (i = 0; i != n*n; ++i) {
            scanf("%d%d%d%d", &up, &down, &left, &_right);
            for (j = 0; j != diff; ++j) //搜索是否是已有卡片
                if (up == map[j][0] && down == map[j][1] && left == map[j][2] && _right == map[j][3])  break;


            if (diff == j){   //如果是新卡片
                numOfCard[j] = 1; //新加一种卡片
                ++diff;
                map[j][0] = up;  map[j][1] = down;
                map[j][2] = left;  map[j][3] = _right;
            }else  ++numOfCard[j];   //这种卡片的数目加1
        }

        if (game != 1) printf("\n");

        printf("Game %d: ", game++);
        if (DFS(0))
            printf("Possible\n");
        else
            printf("Impossible\n");

    }
}