Skip to content

Commit e81c2ac

Browse files
liuyuboboboliuyubobobo
committed
0913 solved.
1 parent 11a07ef commit e81c2ac

File tree

4 files changed

+417
-0
lines changed

4 files changed

+417
-0
lines changed

‎0913-Cat-and-Mouse-Game/cpp-0913/CMakeLists.txt

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
cmake_minimum_required(VERSION 3.5)
2+
project(D)
3+
4+
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
5+
6+
set(SOURCE_FILES main2.cpp)
7+
add_executable(D ${SOURCE_FILES})

‎0913-Cat-and-Mouse-Game/cpp-0913/main.cpp

Lines changed: 221 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,221 @@
1+
/// Source : https://leetcode.com/problems/cat-and-mouse/
2+
/// Author : liuyubobobo
3+
/// Time : 2018-11-04
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <unordered_map>
8+
#include <unordered_set>
9+
#include <stack>
10+
#include <cassert>
11+
#include <queue>
12+
13+
using namespace std;
14+
15+
16+
/// Topological Sorting
17+
/// Create the underlying graph and reverse graph explictly
18+
///
19+
/// Time Complexity: O(node * node * 2 * maxdegree)
20+
/// Space Complexity: O(node * node * 2)
21+
class Solution {
22+
23+
private:
24+
const int DRAW = 0, HOLE = 0, MOUSE = 1, CAT = 2;
25+
26+
public:
27+
int catMouseGame(vector<vector<int>>& graph) {
28+
29+
int n = graph.size();
30+
31+
unordered_map<int, int> dp;
32+
unordered_map<int, unordered_set<int>> g = constructG(graph, dp);
33+
34+
unordered_map<int, unordered_set<int>> rg = reverseG(g);
35+
36+
unordered_map<int, int> degree;
37+
queue<int> q;
38+
for(const pair<int, unordered_set<int>>& p: g){
39+
degree[p.first] = p.second.size();
40+
if(degree[p.first] == 0)
41+
q.push(p.first);
42+
}
43+
44+
while(!q.empty()){
45+
int curkey = q.front();
46+
q.pop();
47+
48+
int curmouse, curcat, curwho;
49+
get(curkey, curmouse, curcat, curwho);
50+
assert(dp.count(curkey));
51+
if(curmouse == MOUSE && curcat == CAT && curwho == MOUSE)
52+
return dp[curkey];
53+
54+
for(int prekey: rg[curkey])
55+
if(!dp.count(prekey)){
56+
int premouse, precat, prewho;
57+
get(prekey, premouse, precat, prewho);
58+
59+
if(prewho == dp[curkey]){
60+
degree[prekey] = 0;
61+
dp[prekey] = dp[curkey];
62+
q.push(prekey);
63+
}
64+
else{
65+
degree[prekey] --;
66+
if(degree[prekey] == 0){
67+
int res = 3 - prewho;
68+
for(int x: g[prekey]){
69+
assert(dp.count(x) && dp[x] != prewho);
70+
if(dp[x] == DRAW){
71+
res = DRAW;
72+
break;
73+
}
74+
}
75+
dp[prekey] = res;
76+
q.push(prekey);
77+
}
78+
}
79+
}
80+
81+
}
82+
return 0;
83+
}
84+
85+
private:
86+
unordered_map<int, unordered_set<int>> reverseG(
87+
const unordered_map<int, unordered_set<int>>& g){
88+
89+
unordered_map<int, unordered_set<int>> res;
90+
for(const pair<int, unordered_set<int>>& p: g){
91+
int u = p.first;
92+
for(int v: p.second)
93+
res[v].insert(u);
94+
}
95+
return res;
96+
}
97+
98+
unordered_map<int, unordered_set<int>> constructG(
99+
const vector<vector<int>>& graph,
100+
unordered_map<int, int>& dp){
101+
102+
unordered_map<int, unordered_set<int>> res;
103+
104+
unordered_set<int> visited;
105+
stack<int> stack;
106+
stack.push(key(MOUSE, CAT, MOUSE));
107+
visited.insert(key(MOUSE, CAT, MOUSE));
108+
while(!stack.empty()){
109+
int curkey = stack.top();
110+
stack.pop();
111+
112+
int curmouse, curcat, curwho;
113+
get(curkey, curmouse, curcat, curwho);
114+
115+
if(curmouse == HOLE){
116+
dp[curkey] = MOUSE;
117+
res[curkey] = unordered_set<int>();
118+
continue;
119+
}
120+
121+
if(curmouse == curcat){
122+
dp[curkey] = CAT;
123+
res[curkey] = unordered_set<int>();
124+
continue;
125+
}
126+
127+
if(curwho == MOUSE){
128+
for(int x: graph[curmouse]){
129+
int nextkey = key(x, curcat, CAT);
130+
res[curkey].insert(nextkey);
131+
if(!visited.count(nextkey)){
132+
visited.insert(nextkey);
133+
stack.push(nextkey);
134+
}
135+
}
136+
}
137+
else{ // curwho == CAT
138+
for(int x: graph[curcat]) if(x){
139+
int nextkey = key(curmouse, x, MOUSE);
140+
res[curkey].insert(nextkey);
141+
if(!visited.count(nextkey)){
142+
visited.insert(nextkey);
143+
stack.push(nextkey);
144+
}
145+
}
146+
}
147+
}
148+
149+
return res;
150+
}
151+
152+
int key(int mousepos, int catpos, int who){
153+
return (mousepos * 100 + catpos) * 100 + who;
154+
}
155+
156+
void get(int key, int& mousepos, int& catpos, int& who){
157+
158+
who = key % 100;
159+
key /= 100;
160+
catpos = key % 100;
161+
mousepos = key / 100;
162+
}
163+
164+
// void printG(const unordered_map<int, unordered_set<int>>& g){
165+
// for(const pair<int, unordered_set<int>>& p: g){
166+
// cout << p.first << " : ";
167+
// for(int e: p.second)
168+
// cout << e << " ";
169+
// cout << endl;
170+
// }
171+
// cout << "----------" << endl;
172+
// }
173+
};
174+
175+
176+
int main() {
177+
178+
vector<vector<int>> g0 = {
179+
{2},{2},{0,1}
180+
};
181+
cout << Solution().catMouseGame(g0) << endl;
182+
// 2
183+
184+
// 2-4-3-1
185+
// |\ /
186+
// 0-5
187+
vector<vector<int>> g1 = {
188+
{2,5},{3},{0,4,5},{1,4,5},{2,3},{0,2,3}
189+
};
190+
cout << Solution().catMouseGame(g1) << endl;
191+
// 0
192+
193+
// 0-2
194+
// | |
195+
// 4-3 1
196+
vector<vector<int>> g2 = {{2,3},{2},{0,1},{0,4},{3}};
197+
cout << Solution().catMouseGame(g2) << endl;
198+
// 2
199+
200+
// 0-2
201+
// /|/
202+
// 1-4 3
203+
vector<vector<int>> g3 = {{2,3,4},{4},{0,3},{0,2},{0,1}};
204+
cout << Solution().catMouseGame(g3) << endl;
205+
// 1
206+
207+
// 0-2-1
208+
// |\|/
209+
// 3-4
210+
vector<vector<int>> g4 = {{2,3,4},{2,4},{0,1,4},{0,4},{0,1,2,3}};
211+
cout << Solution().catMouseGame(g4) << endl;
212+
// 2
213+
214+
vector<vector<int>> g5 = {
215+
{6},{4},{9},{5},{1,5},
216+
{3,4,6},{0,5,10},{8,9,10},{7},{2,7},{6,7}};
217+
cout << Solution().catMouseGame(g5) << endl;
218+
// 1
219+
220+
return 0;
221+
}

0 commit comments

Comments
 (0)