UVa 127 - "Accordian" Patience 数据结构专题

127-"Accordian" Patience

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=63

题目类型： 数据结构， 链表

题意：

发一副牌（52张，分两行）， 从左往右开始， 对于当前这张牌，如果有左边第一个或左边第三个的数值（face-value）或者形状（suit）是一样的，就把该张牌移动到左边第一行或者第三行（如果左1和左3都可以移，则优先移动到左3），移动后，如果继续满足移动条件，则继续移动，直到不能移动为止。 当有一堆牌为空时，要把“空的”消去。

解题思路：

这题就是简单的模拟，对于每一堆牌，用一个栈来保存。 解体的关键关键在于把“空的牌堆”消去的这一过程。 开始时直接用数组做， 但是由于数组删除一个元素要移动很多，效率低，导致TLE。 然后又准备用链表解决。开始时打算用STL的list，但是发现用得很不爽。于是就自己写了用数组实现的链表来做，成功AC。

10269644

127

"Accordian" Patience

Accepted

C++

0.412

2012-06-29 04:26:42

输入：

QD AD 8H 5S 3H 5H TC 4D JH KS 6H 8S JS AC AS 8D 2H QS TS 3S AH 4H TH TD 3C 6S
8C 7D 4C 4S 7S 9H 7C 5D 2S KD 2D QH JD 6D 9D JC 2C KH 3D QC 6C 9S KC 7H 9C 5C
AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC AD 2D 3D 4D 5D 6D 7D 8D TD 9D JD QD KD
AH 2H 3H 4H 5H 6H 7H 8H 9H KH 6S QH TH AS 2S 3S 4S 5S JH 7S 8S 9S TS JS QS KS
#

输出：

6 piles remaining: 40 8 1 1 1 1
1 pile remaining: 52

#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;

int nSize;

struct String{
    char face[3];
};

struct Pile{
     stack<String>face;
}arr[100];
int prev[100], next[100];

// 消除“空的牌堆”
void DelGaps(){
    int i,j;
    for(i=0; i!=nSize; i=next[i]){
        if(arr[i].face.empty()){
            next[prev[i]] = next[i];
            prev[next[i]] = prev[i];
            return ;
        }
    }
}

// 进行移牌
bool Move(){
    int cnt=1;
    for(int i=next[0]; i!=nSize; i=next[i],++cnt){
        int last3, last1;
        if(cnt>2) { // 如果当前位置在3以上，则先判断可不可以移动到左3
            last3 = prev[prev[prev[i]]]; // 获得左3的坐标
            if( arr[i].face.top().face[0]==arr[last3].face.top().face[0]
                    || arr[i].face.top().face[1]==arr[last3].face.top().face[1]){
                arr[last3].face.push(arr[i].face.top() );
                arr[i].face.pop();
                return true;
            }  
        }
        last1= prev[i];  // 获得左1的坐标
        if(arr[i].face.top().face[0]==arr[last1].face.top().face[0] 
                || arr[i].face.top().face[1]==arr[last1].face.top().face[1]){
            arr[last1].face.push(arr[i].face.top());
            arr[i].face.pop();
            return true;
        }
    }
    // 不可一继续移动了，返回false
    return false;
}

void Solve(){
    // 只要可以移动，就一直移动下去
    while(Move())
        DelGaps();  // 每次移动后，到进行消除空堆的过程
}

int main()
{
    freopen("input.txt","r",stdin);
    nSize=0;
    String temp;
    while(scanf("%s", temp.face)){
        if(temp.face[0]=='#') break;
        while(!arr[nSize].face.empty())
            arr[nSize].face.pop();
        arr[nSize].face.push(temp);
        
	
        prev[nSize] = nSize-1;
        next[nSize] = nSize+1;
        ++nSize;
        
        if(nSize==52) {         
            Solve();
            
            int num=0;
            for(int i=0; i!=nSize; i=next[i])
                ++num;
           
            if(num==1) printf("1 pile remaining: ");   // POJ的这题， 这个pile也有加s
            else printf("%d piles remaining: ", num);
            
            for(int i=0; i!=nSize; i=next[i]){
                if(i) printf(" ");
                printf("%d", arr[i].face.size());
            }
            printf("\n");
            nSize=0;
        }
    }
    return 0;
}

—— 生命的意义，在于赋予它意义。

原创http://blog.csdn.net/shuangde800，By D_Double