UVa 10381 - The Rock

Soal ini sudah pernah saya baca sejak tahun 2010, yaitu ketika saya bertekad untuk menyelesaikan soal-soal UVa di chapter 103. Sayangnya, berhari-hari telah saya gunakan untuk memikirkan solusinya dan tidak juga ditemukan :(. Ingin mencari diskusinya di internet pun sumbernya sangat sedikit. Akhirnya pada tahun 2013, saya kembali menantang soal ini dan setelah diskusi dengan Ashar, kami berhasil menyelesaikannya!

Untuk menyelesaikan soal ini, perlu dipahami bahwa soal ini dapat dimodelkan sebagai permainan 2 pemain: satu orang berusaha berjalan sampai pintu keluar (sebut saja A), dan satu orang berusaha memblokir jalan (sebut saja B). Terdapat perbedaan peran yang mana B hanya memiliki kesempatan satu kali memblokir dan dapat dilaksanakan kapan saja. Lalu setelah diblokir, permainan dapat dianggap berakhir karena si pemain yang satunya pasti memilih jalur terpendek. Pertanyaannya adalah: jika keduanya bermain optimal, berapa langkah minimal yang dibutuhkan oleh pemain yang berjalan?

Mari kita sederhanakan persoalannya: anggap peta yang diberikan berbentuk DAG (Directed Acyclic Graph). Untuk menyelesaikan persoalan teori game, kita akan gunakan pendekatan minimax.

Misalkan A sedang di posisi (i, j). Kemungkinan yang dapat terjadi adalah:

1. A bergerak seperti biasa, ke salah satu lokasi yang dapat dia capai.
2. B memblokir salah satu lokasi yang bisa dicapai A, sehingga A harus pergi ke lokasi yang lain.

Bagaimanapun juga, sebenarnya yang memegang kekuasaan apakah kejadian 1 atau 2 yang akan terjadi adalah B. Ketika B merasa pada saat A berada di (i, j) merupakan saat yang tepat untuk memblokir jalan, maka akan langsung dia blokir. Sementara bila tidak, maka dia akan memberikan kesempatan bagi A untuk berjalan. Dengan kata lain, B akan mengambil keputusan yang menghasilkan jarak tempuh sebesar mungkin.

Selanjutnya dapat dirumuskan DP minimax dengan state (i, j), yaitu posisi dimana A berada. Nilai DP ini adalah jarak terkecil yang dibutuhkan apabila pemain A ada di (i, j), dan pemain B masih bisa memblokir jalan. Dirumuskan:

$\displaystyle f(i, j) = \left\{ \begin{array}{lll}   0 & &,(i, j) = finish \\   \max \big{(} & \displaystyle \min_{(ni,nj) \in adj((i,j))} 1 + f(ni,nj), & \\   & \displaystyle \max_{(ni,nj) \in adj((i,j))} g(i,j,ni,nj)  \ \ \big{)}  & ,(i, j) \neq finish \end{array} \right.$

dengan g(i,j,ni,nj) adalah jarak terpendek untuk pergi dari posisi (i, j) menuju ke pintu keluar, dengan petak baris ni dan kolom nj diblokir. Nilai ini bisa di-precompute pada awal eksekusi program dengan BFS. Setelah itu, jalankan DP dari pintu masuk dan persoalan selesai!

Sekarang bagaimana bila persoalannya bukan DAG, melainkan graph secara umum?
Percobaan pertama mungkin berusaha merubahnya menjadi DAG. Sayangnya, saya dan Ashar tidak menemukan caranya. Hal ini menjadi tidak sesederhana biasanya karena melewati jalan yang dekat belum tentu menghasilkan jawaban minimal, sehingga tidak ada kepastian.

Kemudian Ashar menawarkan strategi berikut:
Awali nilai f(i,j) untuk setiap i dan j sebagai tak hingga. Khusus untuk petak pintu keluar, nilainya adalah 0 (pasti benar). Setelah itu, petak-petak yang bertetanggaan dengan petak pintu keluar bernilai 1 (bagaimanapun juga si B memblokir jalan, A pasti bisa sampai pintu keluar dalam 1 langkah). Kemudian untuk petak-petak sisanya, akan diisi sesuai dengan rekurens di atas selama beberapa kali iterasi sampai hasilnya tidak berubah (konvergen). Strategi ini cukup dikenal pada game theory, ketika game state yang ada bersifat siklis (bukan DAG). Kompleksitas solusinya secara keseluruhan (prekomputasi + pencarian solusi) adalah O(R²C² + kRC).

Setelah mencoba strategi tersebut, ternyata AC!
Dari sini saya mempelajari hal baru, yaitu pengulangan iterasi sampai konvergen dalam game theory.

Berikut ini adalah implementasinya:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <utility> #include <vector> #include <queue>   #define REP(a,b) for (int a = 0; a < b; a++) #define FOR(a,b,c) for (int a = b; a <= c; a++) #define RESET(a,b) memset(a,b,sizeof a)   #define PB push_back #define MP make_pair #define F first #define S second #define PII pair<int,int> #define INF 2123123123   #define LL long long #define PUT(a,b) ((a << 10) | b)   using namespace std;   int dr[] = {-1, 0, 1, 0}; int dc[] = {0, -1, 0, 1};   int T; int r,c; char sc[50][50]; int sp[41][41][41][41]; int dp[41][41]; int si,sj,fi,fj; queue<int> q;   // compute sp[ni][nj][i][j]: shortest path from (i,j) with (ni,nj) blocked void precompute(int dist[][41], int fbi, int fbj){    REP(i,r){       REP(j,c){          dist[i][j] = -1;       }    }    dist[fi][fj] = 0;    q.push(PUT(fi,fj));         while (!q.empty()){       int ui = q.front() >> 10;       int uj = q.front() & 1023;       q.pop();               REP(i,4){          int ni = ui + dr[i];          int nj = uj + dc[i];                     if ((0 <= ni) && (ni < r) && (0 <= nj) && (nj < c) && !((ni == fbi) && (nj == fbj))){             if ((dist[ni][nj] == -1) && (sc[ni][nj] != '#')){                dist[ni][nj] = 1 + dist[ui][uj];                q.push(PUT(ni,nj));             }          }       }    } }   int main(){         scanf("%d", &T);    while (T--){       scanf("%d%d", &r, &c);       REP(i,r){          scanf("%s", sc[i]);                     REP(j,c){             if (sc[i][j] == 'X'){                fi = i;                fj = j;             }else if (sc[i][j] == 'E'){                si = i;                sj = j;             }          }       }                REP(i,r){          REP(j,c){             precompute(sp[i][j], i, j);             dp[i][j] = INF;          }       }               // DP base       dp[fi][fj] = 0;       REP(i,4){          int ni = fi + dr[i];          int nj = fj + dc[i];                     if ((0 <= ni) && (ni < r) && (0 <= nj) && (nj < c)){             if (sc[ni][nj] != '#'){                dp[ni][nj] = 1;             }          }       }               // fill until converge       bool change = 1;       while (change){          change = 0;                     REP(i,r){             REP(j,c){                if (abs(i - fi) + abs(j - fj) <= 1) continue;                if (sc[i][j] == '#') continue;                                 // option 1                int op1 = INF;                REP(k,4){                   int ni = i + dr[k];                   int nj = j + dc[k];                                       if ((0 <= ni) && (ni < r) && (0 <= nj) && (nj < c) && (sc[ni][nj] != '#')){                      op1 = min(op1, 1 + dp[ni][nj]);                   }                }                                 // option 2                int op2 = 0;                REP(k,4){                   int ni = i + dr[k];                   int nj = j + dc[k];                                       if ((0 <= ni) && (ni < r) && (0 <= nj) && (nj < c) && (sc[ni][nj] != '#')){                      op2 = max(op2, sp[ni][nj][i][j]);                   }                }                                 int res = max(op1, op2);                if (dp[i][j] != res){                   dp[i][j] = res;                   change = 1;                }             }          }       }               printf("%d\n", dp[si][sj]);    }    return 0; }