This problem involves a BFS simulation on an ice floor grid. The movement mechanics require sliding in a chosen direction until hitting an obstacle. The algorithm explores four directions from each position, continuing to slide until a wall is encountered, at which point the stopping position becomes a new node in the traversal.
Key implementation details include properly marking the starting position as visited and correctly counting all reachable cells.
#include <bits/stdc++.h>
#define ll long long
ll row, col, result, visited[207][207];
char grid[207][207];
const int dirX[] = {0, 1, 0, -1};
const int dirY[] = {1, 0, -1, 0};
bool isValid(int x, int y) {
return grid[x][y] != '#';
}
void breadthFirstSearch() {
std::queue<std::pair<ll, ll>> queue;
queue.push({2, 2});
visited[2][2] = 1;
while (!queue.empty()) {
auto current = queue.front();
queue.pop();
int curX = current.first, curY = current.second;
for (int d = 0; d < 4; ++d) {
int nextX = curX, nextY = curY;
if (isValid(nextX + dirX[d], nextY + dirY[d])) {
while (true) {
int newX = nextX + dirX[d], newY = nextY + dirY[d];
if (isValid(newX, newY)) {
nextX = newX;
nextY = newY;
visited[nextX][nextY]++;
} else {
if (visited[nextX][nextY] <= 1) {
queue.push({nextX, nextY});
}
break;
}
}
}
}
}
}
int main() {
std::cin >> row >> col;
for (int i = 1; i <= row; ++i) {
for (int j = 1; j <= col; ++j) {
std::cin >> grid[i][j];
}
}
breadthFirstSearch();
for (int i = 1; i <= row; ++i) {
for (int j = 1; j <= col; ++j) {
if (visited[i][j] >= 1) result++;
}
}
std::cout << result;
}
B - Strictly Superior
Determine if any product satisfies the strict superiority condition. A product j is strictly superior to product i if:
- The price of j is less thann or equal to price of i
- Product j contains all features that product i has
- Either the price of j is strictly less than i, or j has atleast one feature that i lacks
#include <bits/stdc++.h>
using namespace std;
bool features[105][105];
int prices[105];
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int productCount, featureCount, featureNum;
cin >> productCount >> featureCount;
for (int i = 0; i < productCount; i++) {
cin >> prices[i] >> featureNum;
for (int j = 0; j < featureNum; j++) {
int f;
cin >> f;
features[i][f] = 1;
}
}
for (int i = 0; i < productCount; i++) {
for (int j = 0; j < productCount; j++) {
if (i == j) continue;
if (prices[i] > prices[j]) continue;
int extraFeature = 0;
if (prices[i] < prices[j]) {
for (int f = 0; f < featureCount; f++) {
if (features[j][f] && !features[i][f]) {
extraFeature = 1;
}
}
if (!extraFeature) {
cout << "Yes";
return 0;
}
}
if (prices[i] == prices[j]) {
int jHasExtra = 0, iHasExtra = 0;
for (int f = 0; f < featureCount; f++) {
if (features[j][f] && !features[i][f]) jHasExtra = 1;
if (features[i][f] && !features[j][f]) iHasExtra = 1;
}
if (iHasExtra) {
cout << "Yes";
return 0;
}
}
}
}
cout << "No";
}
C - Reversible
Count distinct strings where a string and its reverse are considered identical. Using a hash map to track visited strings, each new string increments the counter, and both the original and reversed versions are marked as seen.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, distinctCount = 0;
string s;
unordered_map<string, bool> seen;
cin >> n;
while (n--) {
cin >> s;
if (!seen[s]) {
seen[s] = 1;
reverse(s.begin(), s.end());
seen[s] = 1;
distinctCount++;
}
}
cout << distinctCount;
}
E - Vacation Together
Find the maximum length of consecutive columns where every row contains 'o'. Track the current consecutive streak and update the maximum whenever the streak breaks.
#include <bits/stdc++.h>
using namespace std;
bool allAvailable(int colIdx, int numRows, string rows[]) {
for (int i = 0; i < numRows; i++) {
if (rows[i][colIdx] == 'x') {
return false;
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m, currentStreak = 0, maxStreak = 0;
cin >> n >> m;
string rows[105];
for (int i = 0; i < n; i++) {
cin >> rows[i];
}
for (int i = 0; i < m; i++) {
if (allAvailable(i, n, rows)) {
currentStreak++;
} else {
maxStreak = max(currentStreak, maxStreak);
currentStreak = 0;
}
}
maxStreak = max(currentStreak, maxStreak);
cout << maxStreak;
}
H - When?
A simple time calculation problem. Given N minutes from 21:00, output the resulting time in HH:MM format.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
int hour = 21 + n / 60;
int minute = n % 60;
cout << setfill('0') << setw(2) << hour << ":" << setw(2) << minute;
}
I - Rotation
Maintain a pointer to track the starting position of a rotated string. Each rotation operation shifts the starting index, and queries are resolved by calculating the actual position based on the current offset.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m, offset = 0;
string s;
cin >> n >> m >> s;
while (m--) {
int query, param;
cin >> query >> param;
if (query == 2) {
int actualIdx = (offset + param - 1 + n) % n;
cout << s[actualIdx] << endl;
} else if (query == 1 && param % n != 0) {
offset = (offset - param + n) % n;
}
}
}
K - Many Oranges
Calculate the minimum and maximum number of oranges needed to achieve exactly K grams. The maximum count uses the lightest oranges, while the minimum count uses the heaviest oranges.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int minWeight, maxWeight;
double targetWeight;
cin >> minWeight >> maxWeight >> targetWeight;
int targetGrams = targetWeight * 1000;
int maxCount = targetGrams / minWeight;
int minCount = (targetGrams + maxWeight - 1) / maxWeight;
if (minCount > maxCount) {
cout << "UNSATISFIABLE" << endl;
} else {
cout << minCount << " " << maxCount << endl;
}
}
L - Alcoholic
Calculate when cumulative alcohol consumption exceeds the threshold. To avoid floating-point precision issues, multiply the threshold by 100 for integer arithmetic.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, threshold;
cin >> n >> threshold;
threshold *= 100;
long long totalAlcohol = 0;
for (int i = 1; i <= n; i++) {
int volume, percent;
cin >> volume >> percent;
totalAlcohol += (long long)volume * percent;
if (totalAlcohol > threshold) {
cout << i << endl;
return 0;
}
}
cout << -1;
}