問題文: 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; } }