問題B Shuffle'm up

• 問題文(POJ 3087)

練習会では入力形式が少し変更されているので上記のオンラインジャッジで正解するには入力部分のコードを少し書きなおす必要があります。(POJではテストケースの番号+解を出力する)

解法

問題文のとおりに実装しましょう。またいままで訪れた状態はメモしておきましょう。

コード(C++)

#include <iostream>
#include <string>
#include <set>
using namespace std;

int main(){
	int N;
	cin >> N;
	for(int n = 0 ; n < N ; n++ ){
		int C;
		string s1, s2, s12, t;
		set<string> memo;
		cin >> C >> s1 >> s2 >> t;
		
		int ans = 0;
		while( true ){
			ans++;
			s12.clear();
			for(int i = 0 ; i < C ; i++ ){
				s12.push_back( s2[i] );
				s12.push_back( s1[i] );
			}
			s1 = s12.substr(0, C);
			s2 = s12.substr(C, C);
			
			if( s12 == t ){
				break;
			}else if( !memo.count(s12) ){
				memo.insert(s12);
			}else{
				ans = -1;
				break;
			}
		}
		cout << ans << endl;
	}
}