Maze

Jest to zadanie optymalizacyjne z otwartym wejściem, tzn. wszystkie dane wejściowe są jawne i należy wygenerować dane wyjściowe. Wynik jest uzależniony od tego, jak bardzo długość ścieżki jest zbliżona do rozwiązania przygotowanego przez jurorów.

Rozwiązanie z drzewem

W tym zadaniu można zastosować wiele strategii rozwiązania. Podstawowy pomysł jest taki, że graf złożony z pól pustych powinien być drzewem (w przeciwnym bowiem przypadku będziemy mieli „skróty” w grafie, które mogą zostać wykorzystane do skrócenia ścieżki). Ponadto, chcielibyśmy aby drzewo to było jak największe (zatem aby należało do niego jak najwięcej pól pustych) oraz żeby miało jak największą średnicę (żeby istniała długa ścieżka).

Dobrym pomysłem jest zatem stworzenie labiryntu z pól zabronionych ułożonych w przekątne (bo wtedy średnio $2/3$ pól na planszy będzie mogło być puste). Tu przykładowy labirynt wielkości $12\times 12$:

x.#.....#...
.#..#..#..#.
...#..#..#..
..#..#..#..#
.#..#..#..#.
#..#..#..#..
..#..#..#...
.#..#..#..#.
...#..#..#..
..#..#..#..#
.#..#..#..#o
#.....#.....

Poniższy program konstruuje takie labirynty i otrzymuje około $50$ punktów:

const int N = 22;
const int MI[] = {-1,1,0,0}, MJ[] = {0,0,-1,1};
int t,n,m,k;
char b[N][N];
int dist[N][N];
int pre[N][N];
int q[N*N],qe,qb;


int main() {
  scanf("%d",&t);
  while (t-->0) {
    scanf("%d%d%d",&n,&m,&k);

    REP(i,n) REP(j,m) b[i][j] = '.';
    REP(i,n) b[i][m] = 0;
    b[0][0] = 'x';

    REP(i,2*(n+m)) if (i%3==2) {
      int x=i, y=0;
      int xf = -1,yf,xl,yl;
      REP(p,2*(n+m)) {
        if (0 <= x && x < n && 0 <= y && y < m) {
          if (xf == -1) { xf = x; yf = y; }
          xl = x; yl = y;
          b[x][y] = '#';
        }
        --x; ++y;
      }

      if (xf != -1) {
        if (i%6==2) {
          b[xf][yf] = '.';
        } else {
          b[xl][yl] = '.';
        }
      }
    }

    REP(i,n) REP(j,m) dist[i][j] = -1;
    dist[0][0] = 0;
    qe=qb=0;
    q[qe++] = 0;
    while (qe != qb) {
      int v = q[qb++];
      int i = v/N, j=v%N;

      REP(mo,4) {
        int ni = i+MI[mo], nj = j+MJ[mo];
        if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
        if (b[ni][nj] == '#') continue;
        if (dist[ni][nj] != -1) continue;
        dist[ni][nj] = dist[i][j] + 1;
        pre[ni][nj] = v;
        q[qe++] = ni*N + nj;
      }
    }

    REP(ii,k) {
      int fi=-1,fj,maks=0;
      REP(i,n) REP(j,m) if (dist[i][j] > maks) {
        maks = dist[i][j];
        fi=i; fj=j;
      }

      if (fi != -1) {

        b[fi][fj] = 'o';
        while (fi != 0 || fj != 0) {
          dist[fi][fj] = -2;
          int v = pre[fi][fj];
          fi = v/N, fj = v%N;
        }

      } else {
        REP(i,n) REP(j,m) if (b[i][j] == '.') fi=i, fj=j;
        assert(fi != -1);
        b[fi][fj] = 'o';
      }
    }

    REP(i,n) puts(b[i]);
    printf("\n");
  }
}