何回か同じ処理を繰り返すタイプの探索　AOJ1174同色パネル結合

あんまり自分で解いた問題をここに書くことはないけどメモとして。

自分は初めてアルゴリズムっぽいアルゴリズムを勉強したのは、迷路の問題
C - 幅優先探索

幅優先探索や深さ優先探索はかける。いや深さは迷路だとかけるのに他になるとあれ？？再帰呼び出しはどこにかけばいいんだ？再帰がストップする部分はどこにかけばいいんだ？となってしまう。

さて、
1回の試行で選択肢がk個かあって、その試行をn回かするタイプの問題で、単純にk^n回調べればいい問題がある。nが問題で決まっている場合はn重ループをかけばいいんだけど、ダサいのでちゃんと再帰で書く。

再帰しまくりになるとスタックサイズがデカくなって死んでしまうらしい。回避方法はよくしらないので困ってから考えることにする。

0と1をn個ならべるときの全ての場合の列挙

たとえばn = 3のときは000, 001, 010, 011, ... 111というように並べたい.

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)

int S[10];
int n;
void rec(int k){
	if(k == n){
		REP(i,n) cout << S[i] << " ";
		cout << endl;
		return;
	}
	rec(k+1);
	S[k] = 1;
	rec(k+1);
	S[k] = 0;
}

void makecombination(){
	REP(i,n) S[i] = 0;
	rec(0);
}

int main(){
	n = 5;
	makecombination();
}

イメージはなんか、S[k] = 1;でk文字目を1に変更してrec(k+1);で再帰するんだけど、再帰して次の場合を考えるときにはその変更はなかったことにしたい、だからS[k] = 0;する、みたいな感じ。

0からp未満の数字をn個ならべるときの全ての場合の列挙

void rec(int k){
	if(k == n){
		REP(i,n) cout << S[i] << " ";
		cout << endl;
		return;
	}
	rec(k+1);
	REP(i,p){
		S[k] = i;
		rec(k+1);
		S[k] = 0;
	}
}

これも同じようにかける。なんかこう、樹形図をイメージしていくとわかる（自分用のメモなので樹形図は略、ノートに書いた）

同じようにしてAOJ1174　同色パネル結合を解いた。

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)

int h,w,c;
int data[100][100];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int ans;

int check(int grid[100][100]){
	int issearched[100][100] = {0};
	issearched[0][0] = 1;
	int cnt = 1;
	queue<int> qx,qy;
	qx.push(0); qy.push(0);
	while(!qx.empty()){
		int x = qx.front(); int y = qy.front();
		qx.pop(); qy.pop();
		REP(i,4){
			int nx = x + dx[i]; int ny = y + dy[i];
			if(nx > -1 && ny > -1 && nx < h && ny < w && issearched[nx][ny] == 0){
				issearched[nx][ny] = 1;
				if(grid[nx][ny] == c){
					cnt++;
					qx.push(nx); qy.push(ny);
				}
			}
		}
	}
	return cnt;
}

void change(int col,int grid[100][100]){
	int issearched[100][100] = {0};
	queue<int> qx,qy;
	qx.push(0); qy.push(0);
	int stcol = grid[0][0];
	grid[0][0] = col;
	while(!qx.empty()){
		int x = qx.front(); int y = qy.front();
		qx.pop(); qy.pop();
		REP(i,4){
			int nx = x + dx[i]; int ny = y + dy[i];
			if(nx > -1 && ny > -1 && nx < h && ny < w && issearched[nx][ny] == 0){
				issearched[nx][ny] = 1;
				if(grid[nx][ny] == stcol){
					grid[nx][ny] = col;
					qx.push(nx); qy.push(ny);
				}
			}
		}
	}
}

int solve(int n,int grid[100][100]){
	int bgrid[100][100];
	REP(i,h) REP(j,w) bgrid[i][j] = grid[i][j];

	if(n == 4){/*終了条件*/
		change(c,grid); /*最後は1つでも多くしたいので色はc*/
		ans = max(check(grid),ans);/*結果を更新*/
	}else{
		REP(i,6){
			change(i,grid);
			solve(n+1,grid);
			REP(i,h) REP(j,w) grid[i][j] = bgrid[i][j];	//パネルの状態をもどす
		}
	}
	return ans;
}

int main(){
	while(1){
		cin >> h >> w >> c;
		if(h==0) break;
		c--;
		ans = 0;
		REP(i,h) REP(j,w) cin >> data[i][j];
		REP(i,h) REP(j,w) data[i][j]--;
		cout << solve(0,data) << endl;
	}
}