UVa 127 - Accordian Patience 数据结构专题

本文主要是介绍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以上，则先判断可不可以移动到左3last3 = 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;}}// 不可一继续移动了，返回falsereturn 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也有加selse 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;
}

这篇关于UVa 127 - Accordian Patience 数据结构专题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---