AOJ - Problem 1110 : Patience

• 問題文

全探索で解ける問題です。幅優先探索でも深さ優先探索でも解けると思いますが、今回は深さ優先探索で解きました。同じ状態を再び探索しないようにメモしながら探索しました。2枚のカードを取り出したときカードを移動させる処理が少し煩わしいと感じました。

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;


int dx[8] = {-1,0,1,-1,1,-1,0,1};
int dy[8] = {-1,-1,-1,0,0,1,1,1};
int ans;

int card_count(vector<string> c){
	int cnt=0;
	for(int y=0 ; y < 5 ; y++ ){
		for(int x=0 ; x < 4 ; x++ ){
			if( c[y][x] != '*' )
				cnt++;
		}
	}
	return cnt;
}

void shift(vector<string>& c){
	string s;
	for(int y=0 ; y < 5 ; y++ ){
		for(int x=0 ; x < 4 ; x++ ){
			if( c[y][x] != '*' ){
				s.push_back( c[y][x] );
			}
		}
	}
	for(int y=0 ; y < 5 ; y++ ){
		for(int x=0 ; x < 4 ; x++ ){
			if( y*4 + x < s.size() ){
				c[y][x] = s[y*4+x];
			}else{
				c[y][x] = '*';
			}
		}
	}
}

void solve(vector<string> c, map< vector<string> , bool >& m){
	if( m[c] == true ) return;
	m[c] = true;

	for(int y=0 ; y < 5 ; y++ ){
		for(int x=0 ; x < 4 ; x++ ){
			if( c[y][x] == '*' ) continue;

			char ch = c[y][x];
			for(int i=0 ; i < 8 ; i++ ){
				int mx = x + dx[i];
				int my = y + dy[i];
				if( mx < 0 || my < 0 || mx >= 4 || my >= 5 ) continue;
				
				if( ch == c[my][mx] ){
					vector<string> c2 = c;
					c2[y][x] = '*';
					c2[my][mx] = '*';
					shift( c2 );
					int cnt = card_count( c2 );
					ans = min( ans , cnt );
					solve( c2 , m );
				}
			}
		}
	}
}

int main(){
	int n;
	cin >> n;
	for(int i=0 ; i < n ; i++ ){
		vector<string> c;
		map< vector<string> , bool > m;
		for(int y=0 ; y < 5 ; y++ ){
			string s;
			for(int x=0 ; x < 4 ; x++ ){
				char ch;
				cin >> ch;
				s.push_back( ch );
			}
			c.push_back( s );
		}
		ans = 20;
		solve( c , m );
		cout << ans << endl;
	}
}