Дурын граф дээрх тоглоом¶
Дурын $G$ граф дээр хоёр тоглогч тоглоом тоглож байг. Өөрөөр хэлбэл тоглоомын одоогийн төлөв нь тодорхой нэг орой юм. Тоглогчид ээлжлэн нүүдэл хийж, одоогийн оройноос холбогч ирмэгээр дамжин зэргэлдээ орой руу шилжинэ. Тоглоомоос хамааран нүүдэл хийж чадахгүй болсон хүн тоглоомд хожигдох буюу хожно.
Бид хамгийн ерөнхий тохиолдол буюу циклтэй дурын чиглэлтэй графын тохиолдлыг авч үзнэ. Эхний төлөв өгөгдсөн үед хэрэв хоёр тоглогч хоёулаа оновчтой стратегиар тогловол хэн хожихыг тодорхойлох, эсвэл тоглоомын үр дүн тэнцээ болохыг тогтоох нь бидний зорилго юм.
Бид энэ бодлогыг маш үр ашигтайгаар бодно. Бид графын бүх боломжит эхлэх оройн хувьд шийдийг ирмэгийн тоотой шугаман хамааралтай хугацаанд буюу $O(m)$-д олно.
Алгоритмын тайлбар¶
Хэрэв тухайн төлөвөөс эхэлж буй тоглогч оновчтойгоор тогловол (нөгөө тоглогч ямар ч нүүдэл хийхээс үл хамааран) тоглоомд хожих бол уг оройг хожих орой гэж нэрлэнэ. Үүнтэй адил, хэрэв тухайн оройноос эхэлж буй тоглогч өрсөлдөгч нь оновчтойгоор тоглоход тоглоомд хожигдох бол уг оройг хожигдох орой гэж нэрлэнэ.
Графын зарим оройн хувьд бид тэдгээр нь хожих эсвэл хожигдох орой болохыг урьдчилан мэддэг: тухайлбал гарах ирмэггүй бүх орой.
Мөн бидэнд дараах дүрмүүд бий:
- хэрэв орой нь хожигдох орой руу хүргэх гарах ирмэгтэй бол уг орой өөрөө хожих орой болно.
- хэрэв тухайн оройн бүх гарах ирмэг нь хожих орой руу хүргэдэг бол уг орой өөрөө хожигдох орой болно.
- хэрэв ямар нэг цэгт тодорхойлогдоогүй орой үлдсэн бөгөөд эхний ба хоёр дахь дүрмийн аль алинд нь тохирохгүй бол эдгээр орой тус бүрийг эхлэх орой болгон ашиглавал хоёр тоглогч оновчтойгоор тоглоход тэнцээ болно.
Ингэснээр бид $O(n m)$ хугацаанд ажилладаг алгоритмыг шууд тодорхойлж болно. Бид бүх оройг туулж, эхний эсвэл хоёр дахь дүрмийг хэрэглэхийг оролдоод давтана.
Гэвч бид энэ процедурыг хурдасгаж, complexity-г $O(m)$ хүртэл бууруулж болно.
Бид хожих эсвэл хожигдох төлөв эсэхийг нь эхнээсээ мэддэг бүх оройг туулна. Тэдгээр тус бүрийн хувьд бид гүнзгийрүүлэх хайлт эхлүүлнэ. Энэ DFS нь урвуу ирмэгүүдээр ухарч хөдөлнө. Юуны өмнө энэ нь аль хэдийн хожих эсвэл хожигдох орой гэж тодорхойлогдсон орой руу орохгүй. Цаашилбал хэрэв хайлт хожигдох оройноос тодорхойлогдоогүй орой руу явбал бид үүнийг хожих орой гэж тэмдэглэж, энэ шинэ оройг ашиглан DFS-ийг үргэлжлүүлнэ. Хэрэв бид хожих оройноос тодорхойлогдоогүй орой руу явбал энэ оройноос гарах бүх ирмэг хожих орой руу хүргэдэг эсэхийг шалгах ёстой. Бид орой бүрийн хувьд хожих орой руу хүргэх ирмэгийн тоог хадгалснаар энэ шалгалтыг $O(1)$-д гүйцэтгэж болно. Тиймээс хэрэв бид хожих оройноос тодорхойлогдоогүй орой руу явбал тоолуурыг нэмэгдүүлж, энэ тоо нь гарах ирмэгийн тоотой тэнцүү эсэхийг шалгана. Хэрэв тийм бол бид энэ оройг хожигдох орой гэж тэмдэглэж, энэ оройноос DFS-ийг үргэлжлүүлж болно. Эсрэг тохиолдолд энэ орой хожих эсвэл хожигдох орой эсэхийг бид одоохондоо мэдэхгүй тул түүнийг ашиглан DFS-ийг үргэлжлүүлэх нь утгагүй.
Нийтдээ бид хожих ба хожигдох орой бүрийг яг нэг удаа зочилно (тодорхойлогдоогүй оройд зочлохгүй), мөн ирмэг бүрийг хамгийн ихдээ нэг удаа туулна. Иймээс complexity нь $O(m)$ болно.
Implementation¶
Here is the implementation of such a DFS.
We assume that the variable adj_rev stores the adjacency list for the graph in reversed form, i.e. instead of storing the edge $(i, j)$ of the graph, we store $(j, i)$.
Also for each vertex we assume that the outgoing degree is already computed.
vector<vector<int>> adj_rev;
vector<bool> winning;
vector<bool> losing;
vector<bool> visited;
vector<int> degree;
void dfs(int v) {
visited[v] = true;
for (int u : adj_rev[v]) {
if (!visited[u]) {
if (losing[v])
winning[u] = true;
else if (--degree[u] == 0)
losing[u] = true;
else
continue;
dfs(u);
}
}
}
Жишээ: "Цагдаа ба хулгайч"¶
Ийм тоглоомын тодорхой нэг жишээ энд байна.
$m \times n$ хэмжээтэй самбар байна. Зарим нүд рүү орох боломжгүй. Цагдаа болон хулгайчийн эхний координат мэдэгдэж байгаа. Нүднүүдийн нэг нь гарц юм. Хэрэв ямар нэг агшинд цагдаа ба хулгайч нэг нүдэнд байрлавал цагдаа хожно. Хэрэв хулгайч гарцын нүдэнд байвал (цагдаа мөн тэр нүдэнд байхгүй үед) хулгайч хожно. Цагдаа 8 чиглэлд бүгдэд нь явж чадах бол хулгайч зөвхөн 4 чиглэлд (координатын тэнхлэгийн дагуу) явна. Цагдаа болон хулгайч хоёулаа ээлжлэн нүүдэл хийнэ. Гэхдээ тэд хүсвэл нүүдлээ алгасаж болно. Эхний нүүдлийг цагдаа хийнэ.
Одоо бид графыг байгуулна. Үүний тулд бид тоглоомын дүрмийг формал болгох ёстой. Тоглоомын одоогийн төлөв нь цагдаагийн координат $P$, хулгайчийн координат $T$, мөн хэний ээлж болохоор тодорхойлогдоно; энэ хувьсагчийг $P_{\text{turn}}$ гэж нэрлэе (цагдаагийн ээлж бол үнэн байна). Тиймээс графын орой нь $(P, T, P_{\text{turn}})$ гурвалаар тодорхойлогдоно. Дараа нь графыг тоглоомын дүрмийг дагаснаар л амархан байгуулж болно.
Дараа нь бид эхэндээ аль орой нь хожих, аль нь хожигдох орой болохыг тодорхойлох хэрэгтэй. Энд нэг нарийн зүйл бий. Хожих / хожигдох орой нь координатаас гадна $P_{\text{turn}}$ буюу хэний ээлж болохоос мөн хамаарна. Хэрэв цагдаагийн ээлж бол цагдаа ба хулгайчийн координат давхцвал уг орой хожих орой болно; хэрэв энэ нь хожих орой биш бөгөөд хулгайч гарцын оройд байвал уг орой хожигдох орой болно. Хэрэв хулгайчийн ээлж бол хоёр тоглогчийн координат давхцвал уг орой хожигдох орой болно; хэрэв энэ нь хожигдох орой биш бөгөөд хулгайч гарцын оройд байвал уг орой хожих орой болно.
Хэрэгжүүлэхээс өмнөх цорын ганц зүйл бол графыг тодорхой байгуулах уу, эсвэл зүгээр л явцын дунд байгуулах уу гэдгээ шийдэх хэрэгтэй. Нэг талаас графыг тодорхой байгуулах нь илүү хялбар бөгөөд алдаа гаргах магадлал бага. Нөгөө талаас энэ нь кодын хэмжээг нэмэгдүүлэх ба ажиллах хугацаа нь графыг явцын дунд байгуулснаас удаан байна.
Дараах хэрэгжүүлэлт нь графыг тодорхой байгуулна:
struct State {
int P, T;
bool Pstep;
};
vector<State> adj_rev[100][100][2]; // [P][T][Pstep]
bool winning[100][100][2];
bool losing[100][100][2];
bool visited[100][100][2];
int degree[100][100][2];
void dfs(State v) {
visited[v.P][v.T][v.Pstep] = true;
for (State u : adj_rev[v.P][v.T][v.Pstep]) {
if (!visited[u.P][u.T][u.Pstep]) {
if (losing[v.P][v.T][v.Pstep])
winning[u.P][u.T][u.Pstep] = true;
else if (--degree[u.P][u.T][u.Pstep] == 0)
losing[u.P][u.T][u.Pstep] = true;
else
continue;
dfs(u);
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<string> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
for (int P = 0; P < n*m; P++) {
for (int T = 0; T < n*m; T++) {
for (int Pstep = 0; Pstep <= 1; Pstep++) {
int Px = P/m, Py = P%m, Tx = T/m, Ty = T%m;
if (a[Px][Py]=='*' || a[Tx][Ty]=='*')
continue;
bool& win = winning[P][T][Pstep];
bool& lose = losing[P][T][Pstep];
if (Pstep) {
win = Px==Tx && Py==Ty;
lose = !win && a[Tx][Ty] == 'E';
} else {
lose = Px==Tx && Py==Ty;
win = !lose && a[Tx][Ty] == 'E';
}
if (win || lose)
continue;
State st = {P,T,!Pstep};
adj_rev[P][T][Pstep].push_back(st);
st.Pstep = Pstep;
degree[P][T][Pstep]++;
const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
for (int d = 0; d < (Pstep ? 8 : 4); d++) {
int PPx = Px, PPy = Py, TTx = Tx, TTy = Ty;
if (Pstep) {
PPx += dx[d];
PPy += dy[d];
} else {
TTx += dx[d];
TTy += dy[d];
}
if (PPx >= 0 && PPx < n && PPy >= 0 && PPy < m && a[PPx][PPy] != '*' &&
TTx >= 0 && TTx < n && TTy >= 0 && TTy < m && a[TTx][TTy] != '*')
{
adj_rev[PPx*m+PPy][TTx*m+TTy][!Pstep].push_back(st);
++degree[P][T][Pstep];
}
}
}
}
}
for (int P = 0; P < n*m; P++) {
for (int T = 0; T < n*m; T++) {
for (int Pstep = 0; Pstep <= 1; Pstep++) {
if ((winning[P][T][Pstep] || losing[P][T][Pstep]) && !visited[P][T][Pstep])
dfs({P, T, (bool)Pstep});
}
}
}
int P_st, T_st;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == 'P')
P_st = i*m+j;
else if (a[i][j] == 'T')
T_st = i*m+j;
}
}
if (winning[P_st][T_st][true]) {
cout << "Police catches the thief" << endl;
} else if (losing[P_st][T_st][true]) {
cout << "The thief escapes" << endl;
} else {
cout << "Draw" << endl;
}
}