生活随笔
收集整理的這篇文章主要介紹了
POJ 3087 Shuffle'm Up DFS
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
link:http://poj.org/problem?id=3087
題意：給你兩串字串（必定偶數長），按照撲克牌那樣的洗法(每次從S2堆底中拿第一張，再從S1堆底拿一張放在上面)，洗好后的一堆可以把下面的一半作為S1，上面的一半作為S2，問能否洗出題目給出的最終字串。
思路：很好能夠找到規律，就是先把兩串合并，分別存a[i]，a[i+n/2]到新串中，這個新串就是當前洗出的結果。因此進行DFS，由于給出的串長為偶數（？）所以必定能夠洗回初始狀態，所以出口就是初始串。
/** @Date : 2016-11-17-22.11* @Author : Lweleth (SoungEarlf@gmail.com)* @Link : https://github.com/* @Version :*/
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <stack>
#include <queue>
//#include<bits/stdc++.h>
#define LL long long
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std;const int INF = 0x3f3f3f3f;
const int N = 1e5+2000;char a[500];
char b[500];
char c[500];
char t[500];int n;
int ans = 0;
int dfs(char *x, char *y)
{int cnt = 0;for(int i = 0; i < n; i++){x[cnt++] = y[i+n];x[cnt++] = y[i];}x[cnt] = '\0';ans++;if(strcmp(x, b) == 0){//printf("!%s\n", x);return ans;}if(strcmp(x, t) == 0){//printf("~%s\n", x);return -1;}dfs(y, x);
}int main()
{int T;cin >> T;int cnt = 0;while(T--){ans = 0;scanf("%d", &n);scanf("%s", a);scanf("%s", a + n);scanf("%s", b);strcpy(t, a);printf("%d %d\n",++cnt, dfs(c, a));}return 0;
}
轉載于:https://www.cnblogs.com/Yumesenya/p/6086770.html
總結
以上是生活随笔為你收集整理的POJ 3087 Shuffle'm Up DFS的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
