Solution #

In this problem, we could use DFS with memorization, the state is the following four elements: the number of left piles, the top cards on the three rightmost piles. If we could have one pile in the end, the answer is yes. BFS also works for this problem using the same state which might be more intuitive.

Code #

#include <bits/stdc++.h>
using namespace std;
 
const int N=60;
string s[N];
int dp[N][N][N][N];
bool dfs(int n,int i,int j,int k){
	if(n==0) return true;
	int& d=dp[n][i][j][k];
	if(dp[n][i][j][k]) return dp[n][i][j][k]==1?true:false;
	if(s[i][0]==s[j][0]||s[i][1]==s[j][1]){
		if(dfs(n-1,i,k,n-3)){
			return d=1;
		}
	}
	if(n>=3&&(s[i][0]==s[n-3][0]||s[i][1]==s[n-3][1])){
		if(dfs(n-1,j,k,i)){
			return d=1;
		}
	}
	d=-1;
	return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int n;
	cin>>n;
	forn(i,n) cin>>s[i];
	cout<<(dfs(n-1,n-1,n-2,n-3)?"YES":"NO");
    return 0;
}

Solution for Codeforces 208B - Solitaire

Solution #

Code #