Skip to content

Commit f2a35a0

Browse files
liuyuboboboliuyubobobo
committed
0749 solved.
1 parent f8165ca commit f2a35a0

File tree

3 files changed

+149
-0
lines changed

3 files changed

+149
-0
lines changed

‎0501-1000/0749-Contain-Virus/cpp-0749/CMakeLists.txt

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
cmake_minimum_required(VERSION 3.22)
2+
project(cpp_0749)
3+
4+
set(CMAKE_CXX_STANDARD 14)
5+
6+
add_executable(cpp_0749 main.cpp)

‎0501-1000/0749-Contain-Virus/cpp-0749/main.cpp

Lines changed: 141 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,141 @@
1+
/// Source : https://leetcode.com/problems/contain-virus/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-07-19
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <set>
8+
9+
using namespace std;
10+
11+
12+
/// Simulation
13+
/// Time Complexity: O((R * C) ^ 2)
14+
/// Space Compelxity: O(R * C)
15+
class Solution {
16+
17+
private:
18+
const int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
19+
int R, C;
20+
21+
public:
22+
int containVirus(vector<vector<int>>& isInfected) {
23+
24+
R = isInfected.size(), C = isInfected[0].size();
25+
26+
// 0 - not infected, 1 - virus
27+
int res = 0;
28+
while(true){
29+
vector<vector<int>> visited(R, vector<int>(C, -1));
30+
int cc_num = 0;
31+
for(int i = 0; i < R; i ++)
32+
for(int j = 0; j < C; j ++)
33+
if(isInfected[i][j] == 1 && visited[i][j] == -1){
34+
dfs(isInfected, i, j, cc_num ++, visited);
35+
}
36+
37+
if(cc_num == 0) break;
38+
39+
vector<int> walls(cc_num, 0);
40+
vector<set<int>> threaten(cc_num);
41+
for(int i = 0; i < R; i ++)
42+
for(int j = 0; j < C; j ++){
43+
int cc = visited[i][j];
44+
if(cc == -1) continue;
45+
46+
for(int d = 0; d < 4; d ++){
47+
int nx = i + dirs[d][0], ny = j + dirs[d][1];
48+
if(in_area(nx, ny) && isInfected[nx][ny] == 0)
49+
threaten[cc].insert(nx * C + ny), walls[cc] ++;
50+
}
51+
}
52+
53+
int max_threatens = 0, max_cc = -1;
54+
for(int cc = 0; cc < cc_num; cc ++)
55+
if(threaten[cc].size() > max_threatens)
56+
max_threatens = threaten[cc].size(), max_cc = cc;
57+
58+
if(max_threatens == 0) break;
59+
60+
res += walls[max_cc];
61+
for(int i = 0; i < R; i ++)
62+
for(int j = 0; j < C; j ++)
63+
if(visited[i][j] == max_cc) isInfected[i][j] = 2;
64+
65+
vector<vector<int>> next(R, vector<int>(C, 0));
66+
for(int i = 0; i < R; i ++)
67+
for(int j = 0; j < C; j ++){
68+
if(isInfected[i][j] != 1) continue;
69+
for(int d = 0; d < 4; d ++){
70+
int nx = i + dirs[d][0], ny = j + dirs[d][1];
71+
if(in_area(nx, ny) && !isInfected[nx][ny]) next[nx][ny] = 1;
72+
}
73+
}
74+
75+
for(int i = 0; i < R; i ++)
76+
for(int j = 0; j < C; j ++)
77+
if(isInfected[i][j] == 0 && next[i][j])
78+
isInfected[i][j] = 1;
79+
}
80+
return res;
81+
}
82+
83+
private:
84+
void dfs(const vector<vector<int>>& isInfected, int x, int y, int cc,
85+
vector<vector<int>>& visited){
86+
visited[x][y] = cc;
87+
for(int d = 0; d < 4; d ++){
88+
int nx = x + dirs[d][0], ny = y + dirs[d][1];
89+
if(in_area(nx, ny) && isInfected[nx][ny] == 1 && visited[nx][ny] == -1)
90+
dfs(isInfected, nx, ny, cc, visited);
91+
}
92+
}
93+
94+
bool in_area(int x, int y){
95+
return 0 <= x && x < R && 0 <= y && y < C;
96+
}
97+
};
98+
99+
100+
int main() {
101+
102+
vector<vector<int>> isInfected1 = {
103+
{0,1,0,0,0,0,0,1},
104+
{0,1,0,0,0,0,0,1},
105+
{0,0,0,0,0,0,0,1},
106+
{0,0,0,0,0,0,0,0}
107+
};
108+
cout << Solution().containVirus(isInfected1) << '\n';
109+
// 10
110+
111+
vector<vector<int>> isInfected2 = {
112+
{1,1,1,0,0,0,0,0,0},
113+
{1,0,1,0,1,1,1,1,1},
114+
{1,1,1,0,0,0,0,0,0}
115+
};
116+
cout << Solution().containVirus(isInfected2) << '\n';
117+
// 13
118+
119+
vector<vector<int>> isInfected3 = {
120+
{1}
121+
};
122+
cout << Solution().containVirus(isInfected3) << '\n';
123+
// 0
124+
125+
vector<vector<int>> isInfected4 = {
126+
{0,1,0,1,1,1,1,1,1,0},
127+
{0,0,0,1,0,0,0,0,0,0},
128+
{0,0,1,1,1,0,0,0,1,0},
129+
{0,0,0,1,1,0,0,1,1,0},
130+
{0,1,0,0,1,0,1,1,0,1},
131+
{0,0,0,1,0,1,0,1,1,1},
132+
{0,1,0,0,1,0,0,1,1,0},
133+
{0,1,0,1,0,0,0,1,1,0},
134+
{0,1,1,0,0,1,1,0,0,1},
135+
{1,0,1,1,0,1,0,1,0,1}
136+
};
137+
cout << Solution().containVirus(isInfected4) << '\n';
138+
// 38
139+
140+
return 0;
141+
}

‎readme.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -754,6 +754,8 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
754754
| 746 | [Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/) | [solution](https://leetcode.com/problems/min-cost-climbing-stairs/solution/) | [C++](0501-1000/0746-Min-Cost-Climbing-Stairs/cpp-0746/) | | |
755755
| 747 | [Largest Number At Least Twice of Others](https://leetcode.com/problems/largest-number-at-least-twice-of-others/description/) | [solution](https://leetcode.com/problems/largest-number-at-least-twice-of-others/solution/) | [C++](0501-1000/0747-Largest-Number-At-Least-Twice-of-Others/cpp-0747/) | | |
756756
| | | | | | |
757+
| 749 | [Contain Virus](https://leetcode.com/problems/contain-virus/) | [无] | [C++](0501-1000/0749-Contain-Virus/cpp-0749/)| | |
758+
| | | | | | |
757759
| 752 | [Open the Lock](https://leetcode.com/problems/open-the-lock/description/) | [solution](https://leetcode.com/problems/open-the-lock/solution/) | [C++](0501-1000/0752-Open-the-Lock/cpp-0752/) | | |
758760
| 753 | [Cracking the Safe](https://leetcode.com/problems/cracking-the-safe/) | [无] | [C++](0501-1000/0753-Cracking-the-Safe/cpp-0753/) | | |
759761
| 754 | [Reach a Number](https://leetcode.com/problems/reach-a-number/) | [Solution](https://leetcode.com/problems/reach-a-number/solution/) | [C++](0501-1000/0754-Reach-a-Number/cpp-0754/) | | |

0 commit comments

Comments
 (0)