Giả sử, có 2n số chữ cái và mỗi chữ cái có một số nguyên từ 1 đến n được viết trên chúng. Có đúng hai chữ cái có cùng số được viết trên chúng. Các chữ cái này được sắp xếp thành m ngăn xếp và ngăn xếp thứ i có ngăn xếp các chữ cái [i] trên đó. Nhiệm vụ của chúng ta là làm trống tất cả các ngăn xếp theo cách sau
-
Chúng ta phải chọn hai ngăn xếp bất kỳ và loại bỏ chữ cái trên cùng của cả hai ngăn xếp đó.
-
Các chữ cái mà chúng tôi đã xóa phải có cùng số trên cả hai chữ cái.
Nếu chúng ta có thể làm trống m ngăn xếp theo cách này, chúng ta in true hoặc nếu không, chúng ta trả về false.
Vì vậy, nếu đầu vào là n =3, m =2, stacks ={{2, 1, 3}, {2, 1, 3}}, thì đầu ra sẽ là true.
Có hai ngăn xếp và mỗi ngăn xếp có các chữ cái có các số lần lượt là 2, 1, 3 được viết trên chúng. Vì vậy, chúng ta có thể xóa khỏi hai ngăn xếp và làm trống chúng theo cách đã cho.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
Define one 2D array dp
Define an array tvec
for initialize i := 0, when i < m, update (increase i by 1), do:
k := size of stacks[i]
for initialize j := 0, when j < k, update (increase j by 1), do:
if j < 0, then:
insert p at the end of dp[stacks[i, j]]
(increase tvec[p] by 1)
p := stacks[i, j]
Define an array tp
for initialize i := 1, when i <= n, update (increase i by 1), do:
Define one queue q
insert i into q
while (q is not empty), do:
if not tp[first element of q] and tvec[first element of q] is same as 0, then:
for each element next in dp[first element of q], do:
(decrease tvec[next] by 1)
insert next into q
tp[first element of q] := true
delete first element from q
for initialize i := 1, when i <= n, update (increase i by 1), do:
if tvec[i] is not equal to 0, then:
return false
return true Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
bool solve(int n, int m, vector<vector<int>> stacks){
vector<vector<int>> dp(n + 1);
vector<int> tvec(n + 1);
for(int i = 0; i < m; i++){
int k = stacks[i].size();
int p;
for(int j = 0; j < k; j++){
if(j > 0){
dp[stacks[i][j]].push_back(p);
tvec[p]++;
}
p = stacks[i][j];
}
}
vector<bool> tp(n + 1);
for(int i = 1; i <= n; i++){
queue<int> q;
q.push(i);
while(!q.empty()){
if(!tp[q.front()] && tvec[q.front()] == 0){
for(auto next: dp[q.front()]){
tvec[next]--;
q.push(next);
}
tp[q.front()]=true;
}
q.pop();
}
}
for(int i = 1; i <= n; i++){
if(tvec[i] != 0){
return false;
}
}
return true;
}
int main() {
int n = 3, m = 2;
vector<vector<int>> stacks = {{2, 1, 3}, {2, 1, 3}};
cout<< solve(n, m, stacks);
return 0;
} Đầu vào
3, 2, {{2, 1, 3}, {2, 1, 3}} Đầu ra
1