Channel (UVa Live Archive World Finals Harbin 2010)
問題
H*Wの盤面があって、そこに左下から右下へ運河を作る。運河の長さを最大化せよ。
答えは一意に定まる。
2<=H<=20
2<=W<=9
解法
一行分どう接続してるか記憶してメモ化再帰。あとはやるだけ。
#include <stdio.h> #include <string.h> #include <algorithm> #include <iostream> #include <math.h> #include <assert.h> #include <vector> #include <queue> #include <string> #include <map> #include <set> using namespace std; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; static const double EPS = 1e-9; static const double PI = acos(-1.0); #define REP(i, n) for (int i = 0; i < (int)(n); i++) #define FOR(i, s, n) for (int i = (s); i < (int)(n); i++) #define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++) #define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++) #define MEMSET(v, h) memset((v), h, sizeof(v)) int h, w; char field[30][30]; char ans[30][30]; inline int Encode(const char connect[10]) { int ret = 0; REP(i, w + 1) { ret |= (7 & connect[i]) << (i * 3); } return ret; } //int Decode(const ll code, int x) { // int ret = (code >> (x * 4)) & 15; // int v = -(ret >> 3); // ret |= v << 4; // return ret; //} int Calc(int y, int x, const char connect[10]); void Fukugen(int y, int x, const char connect[10]); void PrintConnect(const vector<char> &connect) { REP(i, w + 1) { cout << (int)connect[w - i] << " "; } cout << endl << endl; } int NextState(int y, int x, const char pconnect[10], int wall, int fukugen) { int ny = y; int nx = x + 1; if (nx == w) { nx = 0; ny = y + 1; } char nconnect[10]; memcpy(nconnect + 1, pconnect, sizeof(nconnect) - sizeof(char)); //rotate(nconnect, nconnect + w, nconnect + w + 1); int llc = pconnect[1]; int lc = pconnect[0]; int ruc = pconnect[w - 2]; int uc = pconnect[w - 1]; int luc = pconnect[w]; if (x == 0) { lc = -1; luc = -1; } if (x <= 1) { llc = -1; } if (x == w - 1) { ruc = -1; } if (wall) { nconnect[0] = -1; // ... // .1# if (llc == -1 && luc == -1 && lc != -1 && (y != 0 || x != 1)) { return -1000; } // ?1? // .#. if ((y != 1 || x != 0) && uc >= 0) { return -1000; } // .1 // 2# if (lc != -1 && luc == -1 && uc != -1) { return -1000; } // ???1.2 // 33..#. if (luc < 0) { goto ok1; } REP(i, w) { if (luc == pconnect[i]) { goto ok1; } } return -1000; ok1: // ????11.22 // 333..#... if (uc < 0) { goto ok2; } REP(i, w - 1) { if (uc == pconnect[i]) { goto ok2; } } return -1000; ok2:; } else { nconnect[0] = 7; if (lc == -2 || uc == -2) { return -1000; } // 1?2 // ?C. if (luc != -1 && ruc != -1 && lc == -1) { return -1000; } // ??1 // 1C. if (ruc != -1 && ruc == lc) { return -1000; } // 1. // .C if (lc == -1 && uc == -1 && luc != -1) { return -1000; } // ?1 // 1C if (lc != -1 && lc == uc) { return -1000; } // 1111 // C... if (y == 1 && x == 0 && ruc != -1) { return -1000; } if (lc == -1 && uc == -1) { // .. // .C nconnect[0] = 7; if (x == w - 1) { return -1000; } } else if (uc == -1) { // .?. // ?3C nconnect[0] = lc; if ((luc != -1 || llc != -1) && x != 0) { nconnect[1] = -2; } } else if (lc == -1) { // ?1? // .C. nconnect[0] = uc; if (y != 1 || x != 0) { nconnect[w] = -2; } } else { // .1 -> .1 // 2C 1C nconnect[0] = -2; if (llc != -1) { nconnect[1] = -2; } else { nconnect[1] = uc; } if (y > 1) { nconnect[w] = -2; } REP(i, w + 1) { if (nconnect[i] == lc) { nconnect[i] = uc; } } } } // Normalize { int cnt = 0; char mapto[8]; MEMSET(mapto, -1); for (int i = w; i >= 0; i--) { int v = nconnect[i]; if (v == -1 || v == -2) { continue; } else if (mapto[v] != -1) { nconnect[i] = mapto[v]; } else { nconnect[i] = cnt; mapto[v] = cnt++; } } //assert(cnt < 6); } if (y == 1 && x == 0 && nconnect[w] == -2) { return -1000; } if (y == 0 && x == w - 1 && nconnect[1] == -1 && !wall) { return -1000; } if (fukugen) { Fukugen(ny, nx, nconnect); return 0; } return Calc(ny, nx, nconnect); } map<int, char> memo[22][10]; int Calc(int y, int x, const char connect[10]) { if (y == h) { if (connect[0] != 0) { return -1000; } FOR(i, 1, w + 1) { if (connect[i] >= 0) { return -1000; } } return 0; } int code = Encode(connect); if (memo[y][x].count(code)) { return memo[y][x][code]; } int ret = -100; //cout << "Calc:" << endl; //cout << y << " " << x << " " << ret << endl; //PrintConnect(connect); if (field[y][x] == '#') { ret = NextState(y, x, connect, 1, 0); } else if ((y == h - 1 && x == w - 1) || (y == 0 && x == 0)) { ret = NextState(y, x, connect, 0, 0) + 1; } else { int nret1 = NextState(y, x, connect, 0, 0) + 1; int nret2 = NextState(y, x, connect, 1, 0); ret = max(ret, nret1); ret = max(ret, nret2); } ret = max(ret, -101); return memo[y][x][code] = ret; } void Fukugen(int y, int x, const char connect[10]) { //cout << y << " " << x << endl; if (y == h) { return; } if (field[y][x] == '#') { NextState(y, x, connect, 1, 1); } else if ((y == h - 1 && x == w - 1) || (y == 0 && x == 0)) { ans[y][x] = 'C'; NextState(y, x, connect, 0, 1); } else { int nret1 = NextState(y, x, connect, 0, 0) + 1; int nret2 = NextState(y, x, connect, 1, 0); //assert(nret1 != nret2); if (nret1 > nret2) { ans[y][x] = 'C'; NextState(y, x, connect, 0, 1); } else { NextState(y, x, connect, 1, 1); } } } int main() { int test_case = 0; while (scanf("%d %d", &h, &w), h|w) { test_case++; REP(y, 22) REP(x, 10) { memo[y][x].clear(); } REP(y, h) { scanf("%s", field[y]); } memcpy(ans, field, sizeof(field)); char ini[10]; MEMSET(ini, -1); Calc(0, 0, ini); Fukugen(0, 0, ini); //cout << "Ans: " << Calc(0, 0, ini) << endl; printf("Case %d:\n", test_case); REP(y, h) { puts(ans[y]); } puts(""); } }
