Explanation of Sagheer problem

#1

I want to have the explanation of the code given in the pdf of Sagheer problem.

#2

Please share the code, that you want the explanation for.

#3

The pdf file is not getting attached. It’s available in the Competitive Coding course (under the section: Recursion -VI Advanced Backtracking)

#5

Umm no, I can only see the material associated with your doubt.

So, one way is to ask another doubt from that PDF itself, so that I can access the PDF.

#6

What do you want me to cover in the code?

Hopefully, just the part related to this question, right?

#7 
#include	<ext/pb_ds/assoc_container.hpp>
#include	<ext/pb_ds/tree_policy.hpp>

Is basically for PBDS, there should be a video on this somewhere in your course.

Why taking ll at the end: #define	inf	1000000000000000000ll

It is just to tell the compiler that it is a long long int type number.
That is to prevent accidental integer overflows, like if you write something INF + 2, then it will overflow if you don’t tell the compiler that it is long long int.

This not something very necessary but it is better to keep it so (as an extra measure to be safe).

Here is the code

#include<bits/stdc++.h>
using namespace std;

int n, m;
string rooms[15];
int l[15], r[15];
int ans;

void calc(int i, int dis, bool right) {

	if (i == n - 1) {
		if (right) {
			ans = min(ans, dis + r[i]);
		}
		else {
			ans = min(ans, dis + l[i]);
		}
		return;
	}

	if (right) {
		calc(i + 1, dis + m + 2, 0);
		calc(i + 1, dis + 2 * r[i] + 1, 1);
	}
	else {
		calc(i + 1, dis + m + 2, 1);
		calc(i + 1, dis + 2 * l[i] + 1, 0);
	}

	return;
}

int main()
{
	cin >> n >> m;
	for (int i = n - 1; i >= 0; --i) {
		cin >> rooms[i];
	}

	int max_floor_with_1 = -1;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m + 2; ++j) {
			if (rooms[i][j] == '1') {
				l[i] = max(l[i], j);
			}
			if (rooms[i][m + 1 - j] == '1') {
				r[i] = max(r[i], j);
			}
		}
		if (l[i]) {
			max_floor_with_1 = i;
		}
	}

	n = max_floor_with_1 + 1;

	if (n == 0) {
		cout << 0;
	}
	else if (n == 1) {
		cout << l[0];
	}
	else {
		ans = INT_MAX;

		calc(1, 2 * l[0] + 1, 0);
		calc(1, m + 2, 1);

		cout << ans;
	}

	return 0;
}