読者です 読者をやめる 読者になる 読者になる

AOJ 1174 Identically Colored Panels Connection

AOJ オンラインジャッジ

問題文: Identically Colored Panels Connection | Aizu Online Judge

問題文と戦うゲーム。

正しく問題を把握できて、バグを起こさないコーディングができりゃ勝ち!

左上をひたすら変えまくるのを全通り(6^5)調べるだけ。バックトラックでシミュレーションした。

#include <iostream>
#include <vector>
using namespace std;

int h,w,c;
int data[8][8];


int done[8][8];
int change(int x,int y,int color,int to){
	if(y >= h || x < 0 || y < 0 || x >= w) return 0;
	
	if(data[y][x] != color) return 0;
	else data[y][x] = to;
	
	if(done[y][x] == true) return 0;
	else done[y][x] = true;
	
	int dx[] = {-1,0,1,0};
	int dy[] = {0,1,0,-1};
	for(int i = 0 ; i < 4 ; i++)
		change(x+dx[i] , y+dy[i] , color , to);
}
int count(int x,int y,int color){
	if(y >= h || x < 0 || y < 0 || x >= w) return 0;
	if(data[y][x] != color) return 0;
	if(done[y][x] == true) return 0;
	else done[y][x] = true;
	int ans = 0;
	int dx[] = {-1,0,1,0};
	int dy[] = {0,1,0,-1};
	for(int i = 0 ; i < 4 ; i++)
		ans += count(x+dx[i] , y+dy[i] , color);
	return ans+1;
}
int ans = 0;
int dfs(int n){
	if(n == 5){
		for(int x = 0 ; x < 8 ; x++)
			for(int y = 0 ; y < 8 ; y++)
				done[x][y] = 0;
		ans = max(ans,count(0,0,c));
		return 0;
	}
	
	int tmp[8][8];
	for(int i = 0 ; i < 6 ; i++){
		for(int x = 0 ; x < 8 ; x++)
			for(int y = 0 ; y < 8 ; y++)
				tmp[x][y] = data[x][y] ,done[x][y] = 0;
		change(0,0,data[0][0],i);
		dfs(n+1);
		
		for(int x = 0 ; x < 8 ; x++)
			for(int y = 0 ; y < 8 ; y++)
				data[x][y] = tmp[x][y], done[x][y] = 0;
		
	}
	
}
int main(){
	while(cin >> h >> w >> c , h){
		c--;
		for(int i = 0 ; i < h ; i++)
			for(int j = 0; j < w ; j++)
				cin >> data[i][j] , data[i][j]--;
		ans = 0;
		dfs(0);
		cout << ans << endl;
	}
}