AOJ 1110 Patience
問題文
5*4の20枚のカードがある(1~5)。あるカードと同じ数字の書いてあるカードが隣接(斜めでもよい)していれば、その二つのカードを取り出す。最適な取り出し方をした時、残るカードは何枚か
解法
幅優先探索で解く。状態をメモしておかないと状態数が爆発して、大変なことになるのと、resの初期値をINFにしてしまった。
コード
vii card(5, vi(4)); int N, dy[4] = {-1,0,1,1}, dx[4] = {1,1,1,0}; vii narrow(vii c){ int t; rep(i, 5) rep(j, 4){ if(j){ if(c[i][j-1] != -1) continue; t = c[i][j-1]; c[i][j-1] = c[i][j]; c[i][j] = t; }else{ if(i == 0) continue; if(c[i-1][3] != -1) continue; t = c[i-1][3]; c[i-1][3] = c[i][j]; c[i][j] = t; } } rep(i, 5) rep(j, 4){ if(j){ if(c[i][j-1] != -1) continue; t = c[i][j-1]; c[i][j-1] = c[i][j]; c[i][j] = t; }else{ if(i == 0) continue; if(c[i-1][3] != -1) continue; t = c[i-1][3]; c[i-1][3] = c[i][j]; c[i][j] = t; } } return c; } int csize(vii origin){ int ret = 0; rep(i, 5) rep(j, 4) if(origin[i][j] != -1) ret++; return ret; } int main(){ scanf("%d", &N); while(N--){ rep(i, 5) rep(j, 4) scanf("%d", &card[i][j]); map<vii, bool> m; // memo map queue<vii>q; int res = 20; q.push(card); m[card] = true; while(!q.empty()){ int qsize = (int)q.size(); // fprintf(stderr, "%d\n", qsize); // if(qsize > 1) break; rep(i, qsize){ vii c = q.front(); q.pop(); rep(j, 5) rep(k, 4) rep(d, 4){ vii n = c; int ny = j + dy[d], nx = k + dx[d]; if(!BW(ny, 5) || !BW(nx, 4) || n[ny][nx] != n[j][k]) continue; n[ny][nx] = n[j][k] = -1; n = narrow(n); res = min(res, csize(n)); if(m.count(n) == 0){ m[n] = true; q.push(n); } } } } printf("%d\n", res); } return 0; }