Day 50: Competitive Programming Journal

Date: November 13, 2024
Hello Everyone,

Today marks Day 50 of my competitive programming journey. Here's what I worked on today:

What I Did Today:
I tackled two challenging problems: Solve the Knight’s Tour problem and Find the maximum path sum in a binary matrix.

1. Solve the Knight’s Tour problem (Backtracking):
Problem:
Given an N×N chessboard, the goal is to find a sequence of moves for a knight such that it visits every square exactly once.

Explanation:

• Use backtracking to try all possible knight moves.
• Use a 2D matrix to track the visited squares.
• If all squares are visited, print the path; otherwise, backtrack.

Implementation:

bool isSafe(int x, int y, vector<vector<int>>& board) {
    return (x >= 0 && y >= 0 && x < N && y < N && board[x][y] == -1);
}

bool solveKnightTour(int x, int y, int move, vector<vector<int>>& board, vector<int>& dx, vector<int>& dy) {
    if (move == N * N) return true;

    for (int i = 0; i < 8; i++) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];

        if (isSafe(nextX, nextY, board)) {
            board[nextX][nextY] = move;

            if (solveKnightTour(nextX, nextY, move + 1, board, dx, dy)) {
                return true;
            }

            board[nextX][nextY] = -1;
        }
    }
    return false;
}

2. Find the maximum path sum in a binary matrix:
Problem:

Given a binary matrix, find the maximum path sum from any cell in the first row to any cell in the last row, moving only to the cells below, diagonally left below, or diagonally right below.

Explanation:

• Use dynamic programming to calculate the maximum path sum for each cell, starting from the top row and propagating downwards.

Implementation:

int maxPathSum(vector<vector<int>>& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int up = matrix[i - 1][j];
            int left = (j > 0) ? matrix[i - 1][j - 1] : 0;
            int right = (j < m - 1) ? matrix[i - 1][j + 1] : 0;

            matrix[i][j] += max({up, left, right});
        }
    }

    return *max_element(matrix[n - 1].begin(), matrix[n - 1].end());
}

Reflection:
Both problems tested my problem-solving and implementation skills. The Knight’s Tour problem emphasized the importance of backtracking, while the matrix problem reinforced dynamic programming concepts.

Stay tuned for more updates, and happy coding!