4 files changed, 234 insertions, 0 deletions
diff --git a/week12/ex1.cpp b/week12/ex1.cpp
new file mode 100644
index 0000000..ac00f61
--- /dev/null
+++ b/week12/ex1.cpp
@@ -0,0 +1,63 @@
+#include <iostream>
+
+// Това е значително по-просто решение, аз не се сетих, взех от Катрин Попова
+int knapsack2(int i, int *values, int *weights, int size, int maxWeight) {
+	if (i == size)
+		return 0;
+
+	int currentNotTaken = knapsack2(i+1, values, weights, size, maxWeight);
+
+	if (weights[i] <= maxWeight) {
+		int currentTaken = values[i] + knapsack2(i+1, values, weights, size, maxWeight - weights[i]);
+		return currentTaken > currentNotTaken ? currentTaken : currentNotTaken;
+	}
+	return currentNotTaken;
+}
+
+// Това е решението, показано на практикума
+void knapsack1(int i, int& maxValues, bool *taken, int *values, int *weights, int size, int maxWeight) {
+	if (i == size) {
+		int currentValues = 0, currentWeight = 0;
+		for (int i = 0; i < size; i++) {
+			if (taken[i]) {
+				currentValues += values[i];
+				currentWeight += weights[i];
+			}
+		}
+		if (currentWeight > maxWeight) return;
+		if (currentValues > maxValues) {
+			maxValues = currentValues;
+		}
+		return;
+	}
+
+	taken[i] = false;
+	knapsack1(i+1, maxValues, taken, values, weights, size, maxWeight);
+
+	taken[i] = true;
+	knapsack1(i+1, maxValues, taken, values, weights, size, maxWeight);
+}
+
+int main() {
+	int N;
+	std::cin >> N;
+
+	int *values = new int[N];
+	int *weights = new int[N];
+	for (int i = 0; i < N; i++) {
+		std::cin >> values[i] >> weights[i];
+	}
+	int maxWeight;
+	std::cin >> maxWeight;
+
+	int maxValues = 0;
+	bool *taken = new bool[N];
+	knapsack1(0, maxValues, taken, values, weights, N, maxWeight);
+	std::cout << maxValues << std::endl;
+	delete[] taken;
+
+	std::cout << knapsack2(0, values, weights, N, maxWeight) << std::endl;
+
+	delete[] values;
+	delete[] weights;
+}
diff --git a/week12/ex2.cpp b/week12/ex2.cpp
new file mode 100644
index 0000000..e123ed3
--- /dev/null
+++ b/week12/ex2.cpp
@@ -0,0 +1,45 @@
+#include <iostream>
+
+void floodFill(int row, int col, char** board, int rows, int cols) {
+	if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] == '#')
+		return;
+
+	board[row][col] = '#';
+	floodFill(row+1, col,   board, rows, cols); // up
+	floodFill(row-1, col,   board, rows, cols); // down
+	floodFill(row,   col+1, board, rows, cols); // right
+	floodFill(row,   col-1, board, rows, cols); // left
+}
+
+int main() {
+	int N, M;
+	std::cin >> N >> M;
+
+	char** board = new char*[N];
+	for (int i = 0; i < N; i++) {
+		board[i] = new char[M];
+	}
+
+	for (int i = 0; i < N; i++) {
+		for (int j = 0; j < M; j++) {
+			std::cin >> board[i][j];
+		}
+	}
+
+	int X, Y;
+	std::cin >> X >> Y;
+
+	floodFill(X, Y, board, N, M);
+
+	for (int i = 0; i < N; i++) {
+		for (int j = 0; j < M; j++) {
+			std::cout << board[i][j] << " ";
+		}
+		std::cout << std::endl;
+	}
+
+	for (int i = 0; i < N; i++) {
+		delete[] board[i];
+	}
+	delete[] board;
+}
diff --git a/week12/ex3.cpp b/week12/ex3.cpp
new file mode 100644
index 0000000..e5c64ef
--- /dev/null
+++ b/week12/ex3.cpp
@@ -0,0 +1,58 @@
+#include <iostream>
+
+void markQueen(int valueBy, int row, int col, int board[8][8]) {
+	for (int i = 0; i < 8; i++) {
+		board[row][i] += valueBy;
+	}
+	for (int i = 0; i < 8; i++) {
+		board[i][col] += valueBy;
+	}
+	for (int i = 0; i < 8; i++) {
+		if (row+i < 8  && col+i < 8)
+			board[row+i][col+i] += valueBy;
+		if (row-i > -1 && col-i > -1)
+			board[row-i][col-i] += valueBy;
+	}
+	for (int i = 0; i < 8; i++) {
+		if (row-i > -1 && col+i < 8)
+			board[row-i][col+i] += valueBy;
+		if (row+i < 8  && col-i > -1)
+			board[row+i][col-i] += valueBy;
+	}
+}
+
+void placeQueen(int row, int col, int board[8][8]) {
+	markQueen(1, row, col, board);
+}
+
+void removeQueen(int row, int col, int board[8][8]) {
+	markQueen(-1, row, col, board);
+}
+
+int possibleSolutions(int row, int board[8][8]) {
+	// Board is filled with queens
+	if (row == 8) {
+		// За бонуса, тук просто принтираме целия board
+		return 1;
+	}
+
+	// Find first free column, if any
+	int col = 0;
+	int sum = 0;
+	while (col < 8) {
+		// Place queen temporarily
+		if (board[row][col] == 0) {
+			placeQueen(row, col, board);
+			sum += possibleSolutions(row + 1, board);
+			removeQueen(row, col, board);
+		}
+		col++;
+	}
+
+	return sum;
+}
+
+int main() {
+	int board[8][8] = { { 0 } };
+	std::cout << possibleSolutions(0, board) << std::endl;
+}
diff --git a/week12/ex4.cpp b/week12/ex4.cpp
new file mode 100644
index 0000000..98bbe72
--- /dev/null
+++ b/week12/ex4.cpp
@@ -0,0 +1,68 @@
+#include <iostream>
+
+// Главното неприятно нещо в тази задача е, че трябва да обгърнем вградените оператори във фунцкии
+int add(int a, int b) {
+	return a + b;
+}
+int sub(int a, int b) {
+	return a - b;
+}
+int mul(int a, int b) {
+	return a * b;
+}
+int divi(int a, int b) {
+	return a / b;
+}
+int pow(int a, int b) {
+	int res = 1;
+	while (b-- > 0) {
+		res *= a;
+	}
+	return res;
+}
+
+int recRPN(int (*&op)(int, int), int &on) {
+	int num;
+	std::cin >> num;
+
+	// Ако имаме операция, "връщаме" указател към конкретната функция
+	if (std::cin.fail()) {
+		std::cin.clear();
+		char c;
+		std::cin >> c;
+		if (c == '\'') std::cin >> c;
+
+		switch (c) {
+			case '+': op = add; on = 2; break;
+			case '-': op = sub; on = 2; break;
+			case '*': op = mul; on = 2; break;
+			case '/': op = divi; on = 2; break;
+			case '^': op = pow; on = 2; break;
+			case '$': on = -1; break;
+		}
+		return 0;
+	}
+
+	// Докато не плучим "операция" $, гледаме следващите изрази какво ще върнат
+	do {
+		int rightValue = recRPN(op, on);
+		// Ако сегашната стойност е дясната страна на оператора
+		if (on == 2) {
+			on = 1;
+			return num;
+		}
+		// Ако сегашната стойност е лявата страна на оператора
+		if (on == 1) {
+			on = 0;
+			num = (*op)(num, rightValue);
+		}
+	} while(on > -1);
+
+	return num;
+}
+
+int main() {
+	int (*op)(int, int);
+	int on;
+	std::cout << recRPN(op, on) << std::endl;
+}