2D_Array.cpp

// 🔷 1. Mathematical Foundation of 2D Arrays

// A 2D array is mathematically a matrix:

// A = [a11 a12 a13
//      a21 a22 a23
//      a31 a32 a33]

// i → row index
// j → column index


// 📌 Memory Representation (C++)
// C++ uses Row-Major Order:
//Address of A[i][j] = base + (i × cols + j) × size_of_element
// Address(A[i][j])=base+(i×cols+j)
// 👉 base is the starting address of the array in memory

// 👉 Meaning: entire row is stored continuously in memory.

// 🔷 2. Traversing a 2D Array
// To traverse a 2D array, we use nested loops:
// 🔷 3. Core Traversal Logic
// 🔹 Mathematical Idea

// Traversal = visiting all elements:
// For i from 0 to rows-1:
//     For j from 0 to cols-1:
//         Process A[i][j]
// 🔹 Code Implementation



// 🔷 2. Traversal Techniques
// 🔹 Row-wise Traversal
// for(int i = 0; i < rows; i++) {
//     for(int j = 0; j < cols; j++) {
//         cout << arr[i][j] << " ";
//     }
// }
// 🔹 Column-wise Traversal
// for(int j = 0; j < cols; j++) {
//     for(int i = 0; i < rows; i++) {
//         cout << arr[i][j] << " ";
//     }
// }


#include<bits/stdc++.h>
using namespace std;
int main(){
    int rows,cols;
    cin>>rows>>cols;
    vector<vector<int>>arr(rows,vector<int>(cols));
    //input
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            cin>>arr[i][j];
        }
    }
    //output
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            cout<<arr[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}




// 🔷 1. Row-wise Sum (C++)
// 📌 Concept
// Fix a row i, and add all elements across columns:
// RowSum (i) = ∑ j=0 to cols-1 A[i][j]
// 🔹 Code Implementation



#include<bits/stdc++.h>
using namespace std;
int main(){
    int rows ,cols;
    cin>>rows>>cols;
    vector<vector<int>>arr(rows,vector<int>(cols));
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            cin>>arr[i][j];
        }
    }
    for(int i=0;i<rows;i++){
        int sum=0;
        for(int j=0;j<cols;j++){
            sum+=arr[i][j];
        }
        cout<<sum<<endl;
    }
}


// 🔷 2. Column-wise Sum (C++)
// 📌 Concept

// Fix a column j, and add all elements across rows:
// ColSum
// (j) = ∑ i=0 to rows-1 A[i][j]
// 🔹 Code Implementation






#include<bits/stdc++.h>
using namespace std;
int main(){
    int rows,cols;
    cin>>rows>>cols;
    vector<vector<int>>arr(rows,vector<int>(cols));
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            cin>>arr[i][j];
        }
    }
    for(int j=0;j<cols;j++){
        int sum=0;
        for(int i=0;i<rows;i++){
            sum+=arr[i][j];
        }
        cout<<sum<<endl;
    }
    return 0;
}





// 🔷 4. Important Patterns in 2D Arrays
// 🔹 Matrix Transpose
// Transpose of a matrix A is obtained by swapping rows with columns:
// A^T = [a11 a21 a31
//        a12 a22 a32
//        a13 a23 a33]





#include<bits/stdc++.h>
using namespace std;
int main(){
    int rows,cols;
    cin>>rows>>cols;
    vector<vector<int>>arr(rows,vector<int>(cols));
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            cin>>arr[i][j];
        }
    }
    vector<vector<int>>transpose(cols,vector<int>(rows));
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            transpose[j][i]=arr[i][j];
        }
    }
    for(int i=0;i<cols;i++){
        for(int j=0;j<rows;j++){
            cout<<transpose[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}






// 🔶 (B) Diagonals
// 📌 Primary diagonal: i=j
//📌 Secondary diagonal: i+j=n−1





#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>primary_diagonal;
    vector<int>secondary_diagonal;
    vector<vector<int>>arr(n,vector<int>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>arr[i][j];
            if(i==j){
                primary_diagonal.push_back(arr[i][j]);
            }
            if(i+j==n-1){
                secondary_diagonal.push_back(arr[i][j]);
            }
        }
    }
    cout<<"Primary Diagonal: ";
    for(int i=0;i<primary_diagonal.size();i++){
        cout<<primary_diagonal[i]<<" ";
    }
    cout<<endl;
    cout<<"Secondary Diagonal: ";
    for(int i=0;i<secondary_diagonal.size();i++){
        cout<<secondary_diagonal[i]<<" ";
    }
    cout<<endl;
    return 0;
}









// 5🔹 Spiral Traversal

// Algorithm:
// Top row
// Right column
// Bottom row
// Left column

// int top = 0, bottom = rows - 1;
// int left = 0, right = cols - 1;

// while(top <= bottom && left <= right) {

//     for(int i = left; i <= right; i++)
//         cout << arr[top][i] << " ";
//     top++;

//     for(int i = top; i <= bottom; i++)
//         cout << arr[i][right] << " ";
//     right--;

//     if(top <= bottom) {
//         for(int i = right; i >= left; i--)
//             cout << arr[bottom][i] << " ";
//         bottom--;
//     }

//     if(left <= right) {
//         for(int i = bottom; i >= top; i--)
//             cout << arr[i][left] << " ";
//         left++;
//     }
// }

//🔷 6. Spiral Traversal




#include<bits/stdc++.h>
using namespace std;
int main(){
    int rows,cols;
    cin>>rows>>cols;
    vector<vector<int>>arr(rows,vector<int>(cols));
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            cin>>arr[i][j];
        }
    }
    // Spiral traversal logic would go here
    int top=0,bottom=rows-1;
    int left=0,right=cols-1;
    while(top<=bottom && left<=right){
        for(int i=left;i<=right;i++){
            cout<<arr[top][i]<<" ";
        }
        top++;
        for(int i=top;i<=bottom;i++){
            cout<<arr[i][right]<<" ";
        }
        right--;
        if(top<=bottom){
            for(int i=right;i>=left;i--){
                cout<<arr[bottom][i]<<" ";
            }
            bottom--;
        }
        if(left<=right){
            for(int i=bottom;i>=top;i--){
                cout<<arr[i][left]<<" ";
            }
            left++;
        }
    }
    return 0;
}




// 🔷 7. Matrix Operations (Mathematical)
// 🔹 Matrix Addition
// C = A + B
// C[i][j] = A[i][j] + B[i][j]
// 🔹 Matrix Multiplication
// C = A × B
// C[i][j] = ∑ k=0 to n-1 A[i][k] × B[k][j]
// 🔹 Matrix Transpose
// C = A^T
// C[i][j] = A[j][i]
// 🔹 Matrix Determinant (for 2x2)
// det(A) = a11*a22 - a12*a21
// 🔹 Matrix Inverse (for 2x2)
// A^-1 = (1/det(A)) * adj(A)
// where adj(A) is the adjugate of A
//subtract two matrices
// C = A - B
// C[i][j] = A[i][j] - B[i][j]
// 🔹 Scalar Multiplication
// C = k * A
// C[i][j] = k * A[i][j]
// 🔹 Identity Matrix
// C = I
// C[i][j] = 1 if i == j, else 0
// 🔹 Zero Matrix
// C = 0
// C[i][j] = 0 for all i, j
// 🔹 Matrix Power
// C = A^k
// C = A × A × ... × A (k times)
// 🔹 Matrix Rank
// rank(A) = number of linearly independent rows (or columns)
// 🔹 Matrix Trace
// trace(A) = sum of elements on the main diagonal
// trace(A) = ∑ i=0 to n-1 A[i][i]
// 🔹 Matrix Symmetry
// A is symmetric if A = A^T
// A[i][j] = A[j][i] for all i, j
// 🔹 Matrix Skew-Symmetry
// A is skew-symmetric if A = -A^T
// A[i][j] = -A[j][i] for all i, j
// 🔹 Matrix Orthogonality
// A is orthogonal if A^T = A^-1
// A^T × A = I
// 🔹 Matrix Eigenvalues and Eigenvectors
// A * v = λ * v
// where λ is an eigenvalue and v is the corresponding eigenvector
// 🔹 Matrix Diagonalization
// A = PDP^-1
// where D is a diagonal matrix of eigenvalues and P is a matrix of corresponding eigenvectors
// 🔹 Matrix Rank-Nullity Theorem
// rank(A) + nullity(A) = number of columns in A
// 🔹 Matrix Row Reduction (Gaussian Elimination)
// 🔹 Matrix LU Decomposition
// A = LU
// where L is a lower triangular matrix and U is an upper triangular matrix








// 🔹 Matrix Addition implementation


#include<bits/stdc++.h>
using namespace std;
int main(){
    int rows,cols;
    cin>>rows>>cols;
    vector<vector<int>>A(rows,vector<int>(cols));
    vector<vector<int>>B(rows,vector<int>(cols));
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            cin>>A[i][j];
        }
    }
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            cin>>B[i][j];
        }
    }
    vector<vector<int>>C(rows,vector<int>(cols));
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            C[i][j]=A[i][j]+B[i][j];
        }
    }
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            cout<<C[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}







// 🔹 Matrix Multiplication implementation


#include<bits/stdc++.h>
using namespace std;
int main(){
    int rowsA,colsA,rowsB,colsB;
    cin>>rowsA>>colsA;
    cin>>rowsB>>colsB;
    if(colsA!=rowsB){
        cout<<"matrix multiplication are not posible"<<endl;
        return 0;
    }
    vector<vector<int>>A(rowsA,vector<int>(colsA));
    vector<vector<int>>B(rowsB,vector<int>(colsB));
    for(int i=0;i<rowsA;i++){
        for(int j=0;j<colsA;j++){
            cin>>A[i][j];
        }
    }
    for(int i=0;i<rowsB;i++){
        for(int j=0;j<colsB;j++){
            cin>>B[i][j];
        }
    }
    vector<vector<int>>C(rowsA,vector<int>(colsB));
    for(int i=0;i<rowsA;i++){
        for(int j=0;j<colsB;j++){
            C[i][j]=0;
            for(int k=0;k<colsA;k++){
                C[i][j]+=A[i][k]*B[k][j];
            }
        }
    }
    for(int i=0;i<rowsA;i++){
        for(int j=0;j<colsB;j++){
            cout<<C[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}



// 🔹 Matrix Determinant (for 2x2)
// det(A) = a11*a22 - a12*a21




#include<bits/stdc++.h>
using namespace std;
int main(){
    int rows,cols;
    cin>>rows>>cols;
    if(rows!=2|| cols!=2){
        cout<<"Determinant is only for 2*2 matrices"<<endl;
        return 0;
    }
    vector<vector<int>>A(rows,vector<int>(cols));
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            cin>>A[i][j];
        }
    }
    int determinant=A[0][0]*A[1][1]-A[0][1]*A[1][0];
    cout<<"Determinant: "<<determinant<<endl;
    return 0;
}






// 🔷 6. Prefix Sum (Very Important)
// 📌 Mathematical Formula
// prefix[i][j] = A[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
// Explanation:
// prefix[i][j] = A[i][j] + top + left - overlap
// where:
// top = prefix[i-1][j]
// left = prefix[i][j-1]
// overlap = prefix[i-1][j-1]

// 🔷 1. What is Prefix Sum?

// 👉 Prefix sum means precomputing cumulative sums so that future queries become very fast.
// 🔹 1D Idea First (Easy Understanding)
// Given array:
// [2, 4, 1, 3, 5]
// Prefix sum:
// [2, 6, 7, 10, 15]
// 📌 Formula
// prefix[i]=prefix[i−1]+arr[i]
// 🔹 Why?

// 👉 To quickly find sum of any subarray:
// sum(L,R)=prefix[R]−prefix[L−1]

// 🔷 2. 2D Prefix Sum (Main Concept)
// Now extend to matrix.

// 🔹 Given Matrix
// 1 2 3
// 4 5 6
// 7 8 9
// 🔹 Prefix Matrix Meaning
// 👉 prefix[i][j] = sum of all elements from (0,0) to (i,j)
// 🔷 3. Mathematical Formula (VERY IMPORTANT)
// prefix[i][j] = A[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
// 🔥 Why subtract?
// 👉 Because overlap is counted twice:
// top area
// left area
// 👉 overlap counted twice → subtract once
// 🔷 4. Step-by-Step Example

// Matrix:
// 1 2 3
// 4 5 6
// 7 8 9
// 🔹 Calculate prefix[1][1] (value = 5)

//=5+(top=2)+(left=4)−(overlap=1)
// =5+2+4−1=10
// Final Prefix Matrix
// 1   3   6
// 5  12  21
// 12 27  45
//🔷 5. How to Use Prefix Sum (Main Purpose)

// 👉 To find sum of any submatrix quickly
// 📌 Formula
// For rectangle:
// Top-left = (r1, c1)
// Bottom-right = (r2, c2)
//sum=prefix[r2][c2]−prefix[r1−1][c2]−prefix[r2][c1−1]+prefix[r1−1][c1−1]
// 🔥 Why?

// Same idea:
// Take full rectangle
// Remove extra parts
// Add overlap back



#include<bits/stdc++.h>
using namespace std;
int main(){
    int rows,cols;
    cin>>rows>>cols;
    vector<vector<int>>A(rows,vector<int>(cols));
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            cin>>A[i][j];
        }
    }
    vector<vector<int>>prefix(rows,vector<int>(cols));
   for(int i=0;i<rows;i++){
     for(int j=0;j<cols;j++){
            int top=(i>0)?prefix[i-1][j]:0;
            int left=(j>0)?prefix[i][j-1]:0;
            int overlap=(i>0 && j>0)?prefix[i-1][j-1]:0;
            prefix[i][j]=A[i][j]+top+left-overlap;
     }
   }
   for(int i=0;i<rows;i++){
    for(int j=0;j<cols;j++){
        cout<<prefix[i][j]<<" ";
    }
    cout<<endl;
   }
   return 0;
}





// 🔷 1. Linear Search in 2D Array
// 📌 Algorithm (Step-by-step)
// Traverse each row
// Traverse each column
// Compare element with key
// If match → print position
// 🧠 Mathematical Idea
// ∀i∈[0,n),∀j∈[0,m)
// 👉 Check every element → brute force
// ⏱ Time Complexity  :O(n×m)



#include<bits/stdc++.h>
using namespace std;
int main(){
    int rows,cols,key;
    cin>>rows>>cols>>key;
    vector<vector<int>>arr(rows,vector<int>(cols));
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            cin>>arr[i][j];
        }
    }
    bool found=false;
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            if(arr[i][j]==key){
                cout<<"element found at position:"<<i<<" "<<j<<endl;
                found=true;
                break;
            }
        }
        if(found){
            break;
        }

    }
    if(!found){
        cout<<"element not found"<<endl;
    }
    return 0;
}




// 🔷 1. Core Idea: Grid = Graph
// 👉 Think of the grid as a graph:
// Each cell → Node
// Movement (up/down/left/right) → Edges
// Example grid:
// 1 1 0
// 0 1 0
// 1 0 1
// 👉 Each (i, j) is a node.
// 🔷 2. What is BFS?
// 👉 BFS (Breadth First Search) explores nodes level by level
// First → starting node
// Then → all neighbors
// Then → neighbors of neighbors
// 👉 Uses Queue (FIFO)

// 🔷 3. Movement in Grid

// You defined:

// int dx[] = {1, -1, 0, 0};
// int dy[] = {0, 0, 1, -1};

// 👉 These represent directions:

// Direction	dx	dy
// Down     	+1	 0
// Up	        -1   0
// Right	     0	+1
// Left	         0	-1

// 🔷 4. BFS Algorithm in Grid
// 1. Initialize queue and visited array
// 2. Enqueue starting node (x, y) and mark visited
// 3. While queue not empty:
//     a. Dequeue node (cx, cy)
//     b. For each direction (dx[i], dy[i]):
//         i. Calculate new position (nx, ny) = (cx + dx[i], cy + dy[i])
//         ii. Check if (nx, ny) is within bounds and not visited
//         iii. If valid → Enqueue (nx, ny) and mark visited
// 4. Continue until queue is empty or target found



#include<bits/stdc++.h>
using namespace std;
int main(){
    int rows,cols;
    cin>>rows>>cols;
    vector<vector<int>>grid(rows,vector<int>(cols));
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            cin>>grid[i][j];
        }
    }
    int dx[]={1,-1,0,0};
    int dy[]={0,0,1,-1};
    vector<vector<bool>>visited(rows,vector<bool>(cols,false));
    queue<pair<int,int>>q;
    // Starting point (0, 0)
    q.push({0,0});
    visited[0][0]=true;
    while(!q.empty()){
        auto current=q.front();
        q.pop();
        int cx=current.first;
        int cy=current.second;
        cout<<"Visited: "<<cx<<" "<<cy<<endl;
        for(int i=0;i<4;i++){
            int nx=cx+dx[i];
            int ny=cy+dy[i];
            // Check bounds and visited
            if(nx>=0 && nx<rows && ny>=0 && ny<cols && !visited[nx][ny]){
                q.push({nx,ny});
                visited[nx][ny]=true;
            }
        }

    }
    return 0;

}












// 🔷 1. What DFS Really Means
// 👉 DFS (Depth First Search) =
// Go as deep as possible in one direction, then backtrack and try other directions.
// 🔶 Simple Idea
// From one cell:
// Go down as far as possible
// Then try up
// Then right
// Then left

// 👉 One path fully → then next path
// 🔷 2. Grid = Graph (Important Understanding)
// For a matrix:
// 1 1 0
// 0 1 0
// 1 0 1


// 👉 Treat as graph:

// Each cell = node
// Moves (up, down, left, right) = edges
// 🔷 3. Your Code (Understanding First)
// void dfs(int i, int j, vector<vector<int>>& grid) {
//     if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size())
//         return;

//     dfs(i+1, j, grid);
//     dfs(i-1, j, grid);
//     dfs(i, j+1, grid);
//     dfs(i, j-1, grid);
// }
// 🔴 Problem in Your Code
// 👉 This code is incomplete ❌

// Why?
// No visited check
// Will revisit same cell again and again
// 👉 Leads to infinite recursion / crash
// 🔷 4. Correct DFS (Full Logic)

// 👉 You must:

// Check boundary
// Check if already visited
// Mark visited
// Explore neighbors



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

   void dfs(int i,int j,vector<vector<int>>&grid,vector<vector<bool>>&visited){
        // Boundary check
        int rows=grid.size();
        int cols=grid[0].size();
        if(i<0||j<0||i>=rows||j>=cols||grid[i][j]==0||visited[i][j]){
            return;
        }
        // Mark visited
        visited[i][j]=true;
  //  PRINT HERE
    cout << "Visited: " << i << "," << j << endl;
        // Explore neighbors
        dfs(i+1,j,grid,visited); // down
        dfs(i-1,j,grid,visited); // up
        dfs(i,j+1,grid,visited);//right
        dfs(i,j-1,grid,visited);//left
    } 
int main(){
    int rows,cols;
    cin>>rows>>cols;
    vector<vector<int>>grid(rows,vector<int>(cols));
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            cin>>grid[i][j];
        }
    }
    vector<vector<bool>>visited(rows,vector<bool>(cols,false));
 
    dfs(0, 0, grid, visited);
    return 0;
}




// 🔶 4. Dynamic Programming (Grid)
// 📌 Unique Paths Formula
// dp[i][j]=dp[i−1][j]+dp[i][j−1]
// Explanation:
// To reach (i, j):
// From top (i-1, j)
// From left (i, j-1)
// Base Cases:
// dp[0][0] = 1 (starting point)
// dp[i][0] = 1 (only one way down)
// dp[0][j] = 1 (only one way right)
// 🔷 5. Unique Paths in Grid (DP Implementation)


// 🔷 7. Time & Space Complexity
// Type	Value
// Time	O(rows × cols)
// Space	O(rows × cols)
// 🔷 8. Mathematical Insight (Advanced 🔥)
// 👉 This is also a combinatorics problem
// Total moves:
// Right = (cols - 1)
// Down = (rows - 1)
// Total steps:(rows+cols−2)

// Number of unique paths = C(steps, right) = C(steps, down)​
// C(steps, right) = (steps)! / (right! * down!)
// 🔷 9. Intuition (Very Important)
// 👉 Each cell = sum of ways to reach it
// 👉 Like building paths step-by-step
// 🔷 🧠 Final Understanding
// ✔ Move only right or down
// ✔ Each cell depends on top + left
// ✔ Build solution using DP
// 🔥 One-Line Summary
// 👉 Number of ways to reach a cell = ways from top + ways from left




#include<bits/stdc++.h>
using namespace std;
int main(){
    int rows,cols;
    cin>>rows>>cols;
    vector<vector<int>>dp(rows,vector<int>(cols));
    for(int i=0;i<rows;i++){
        dp[i][0]=1;
    }
    for(int j=0;j<cols;j++){
        dp[0][j]=1;
    }
    for(int i=1;i<rows;i++){
        for(int j=1;j<cols;j++){
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
    }
    cout<<"Number of unique paths from (0,0) to ("<<rows-1<<","<<cols-1<<") is: "<<dp[rows-1][cols-1]<<endl;
    return 0;
}









// 🔷 1. What is Backtracking?
// 👉 Backtracking =
// Try a path → if it fails → go back → try another path
// 🔶 Simple Idea
// Like solving a maze:
// Try moving
// If stuck → go back
// Try another direction
// 🔷 2. Your Code Concept
// bool solve(int x, int y, vector<vector<int>>& maze)
// 👉 This function checks:
// Can we reach destination from (x,y)?
// 🔷 3. Problem Understanding
// 👉 Maze:
// 1 → allowed path
// 0 → blocked
// 👉 Start: (0,0)
// 👉 End: (n-1,n-1)
// 👉 Moves allowed:
// Right ➡️
// Down ⬇️
// 🔷 4. Step-by-Step Logic
// 📌 Step 1: Base Case (Reached Destination)
// if(x == n-1 && y == n-1) return true;
// 👉 If reached end → success ✅
// 📌 Step 2: Invalid Case
// if(x >= n || y >= n || maze[x][y] == 0) return false;
// 👉 Stop if:
// Out of bounds
// Blocked cell
// 📌 Step 3: Mark Visited
// maze[x][y] = 0;

// 👉 Prevent revisiting same cell
// 📌 Step 4: Explore Paths
// if(solve(x+1, y, maze) || solve(x, y+1, maze))

// 👉 Try:
// Down
// Right
// 📌 Step 5: Return Result
// return true / false;


// 🔶 Maze:
// 1 1 0
// 1 1 1
// 0 1 1
// 🔷 Path Found
// 👉 One valid path:
// (0,0) → (1,0) → (1,1) → (1,2) → (2,2)


// 🔷 7. How Backtracking Works Here
// 🔶 Step Flow
// Start at (0,0)
// Try going down
// If blocked → go right
// If dead end → backtrack
// 🔥 Important

// 👉 If path fails:

// Function returns false
// Automatically goes back (backtracking)
// 🔷 8. Why It's Called Backtracking

// 👉 Because:

// Try path
// If fail → return → try next
// 🔷 9. Time Complexity

// 👉 Worst case:  O(2^n^2)
//👉 Because many paths possible




#include<bits/stdc++.h>
using namespace std;
int n;
bool solve(int x,int y,vector<vector<int>>&maze){
    // base case
    if(x==n-1 && y==n-1){
        return true;
    }
    //invalid case
    if(x>=n || y>=n || maze[x][y]==0){
        return false;
    }
    //mark visited
    maze[x][y]=0;
    //explore paths
    if(solve(x+1,y,maze) || solve(x,y+1,maze)){
        return true;
    }
    return false;
}
int main(){
cin>>n;
vector<vector<int>>maze(n,vector<int>(n));
for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        cin>>maze[i][j];
    }
}
if(solve(0,0,maze)){
    cout<<"Path found from (0,0) to ("<<n-1<<","<<n-1<<")"<<endl;
}
else{
    cout<<"No path exists from (0,0) to ("<<n-1<<","<<n-1<<")"<<endl;
}
}





// 🔷 8. Advanced Problem: Number of Islands
// 📌 Concept:

// DFS + Connected Components
// 🔶 Problem Statement
// Given a grid of '1's (land) and '0's (water), count the number of islands.
// An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
// 🔷 9. Solution Approach
// 1. Initialize count = 0
// 2. Traverse each cell in the grid
// 3. If cell is '1':
//     a. Increment count
//     b. Perform DFS to mark all connected '1's as visited (turn them to '0')
// 4. Continue until all cells are processed


// 🔷 1. Problem Understanding
// You are given a grid:
// '1' → land
// '0' → water
// 👉 An island = group of connected '1' cells (up, down, left, right)
// 🔶 Goal
// 👉 Count how many separate islands exist
// 🔷 2. Core Concept
// 👉 This is a Connected Components problem
// Each island = one connected component
// 🔷 3. Key Idea
// 👉 Traverse grid
// 👉 When you find '1':

// Start DFS
// Mark entire island as visited
// Increase count
// 🔷 4. Your DFS Code (Explanation)
// void dfs(int i, int j, vector<vector<char>>& grid)

// 👉 This explores one full island
// 🔶 Step-by-Step
// 📌 Base Condition
// if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == '0')
//     return;
// 👉 Stop if:

// Out of bounds
// Water
// Already visited
// 📌 Mark Visited
// grid[i][j] = '0';

// 👉 Convert land → water
// 👉 Prevent revisiting

// 📌 Explore 4 Directions
// dfs(i+1, j, grid);
// dfs(i-1, j, grid);
// dfs(i, j+1, grid);
// dfs(i, j-1, grid);





// 👉 Visit entire island

#include<bits/stdc++.h>
using namespace std;
void dfs(int i,int j,vector<vector<char>>&grid){
    if(i<0||j<0||i>=grid.size()||j>=grid[0].size()||grid[i][j]=='0'){
        return;
    }
    grid[i][j]='0';
    dfs(i+1,j,grid);
    dfs(i-1,j,grid);
    dfs(i,j+1,grid);
    dfs(i,j-1,grid); 
}
int main(){
    int rows,cols;
    cin>>rows>>cols;
    vector<vector<char>>grid(rows,vector<char>(cols));
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            cin>>grid[i][j];
        }
    }
    int cnt=0;
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            if(grid[i][j]=='1'){
                cnt++;
                dfs(i,j,grid);
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}





// 🔷 1. What is Matrix Rotation?

// 👉 Rotating a matrix means:

// Changing positions of elements
// Usually by 90°, 180°, 270°
// 🔷 2. Types of Rotation
// 🔶 1. 90° Clockwise
// 🔶 2. 90° Anti-clockwise
// 🔶 3. 180° Rotation




// 🔷 3. Example Matrix
// 1 2 3
// 4 5 6
// 7 8 9
// 🔷 4. 🔶 90° Clockwise Rotation
// ✅ Output
// 7 4 1
// 8 5 2
// 9 6 3
// 🔷 🔥 Key Idea (VERY IMPORTANT)

// 👉 2 steps:
// 1. Transpose the matrix
// 2. Reverse each row

// 🔷 7. Mathematical Mapping
// 🔶 Clockwise:(i,j)→(j,n−i−1) or (i,j)->(j,n-i-1)
// 🔶 Anti-clockwise:(i,j)→(n−j−1,i)
// 🔶 180°:(i,j)→(n−i−1,n−j−1)


// 90° Clockwise

#include<bits/stdc++.h>
using namespace std;
void rotate90Clockwise(vector<vector<int>>&matrix){
    int n=matrix.size();
    // Step 1: Transpose
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            swap(matrix[i][j],matrix[j][i]);
        }
    }
    // Step 2: Reverse each row
    for(int i=0;i<n;i++){
        reverse(matrix[i].begin(),matrix[i].end());
    }
}
int main(){
    int n;
    cin>>n;
    vector<vector<int>>matrix(n,vector<int>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>matrix[i][j];
        }
    }
    rotate90Clockwise(matrix);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<matrix[i][j]<<" ";
        }
        cout<<endl;

    }
    return 0;
}




// 90° Anti-clockwise



#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<vector<int>>matrix(n,vector<int>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>matrix[i][j];
        }
    }
    //step-1:transpose
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            swap(matrix[i][j],matrix[j][i]);
        }
    }
    //step-2:reverse each column
    for(int j=0;j<n;j++){
        for(int i=0;i<n/2;i++){
            swap(matrix[i][j],matrix[n-1-i][j]);
        }

    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<matrix[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}
  




// 180° Rotation

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<vector<int>>matrix(n,vector<int>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>matrix[i][j];
        }
    }
      // Step 1: Reverse rows (top to bottom)
       reverse(matrix.begin(), matrix.end());
    //step-2:reverse each row
    for(int i=0;i<n;i++){
        reverse(matrix[i].begin(),matrix[i].end());
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<matrix[i][j]<<" ";
        }
        cout<<endl;
    }

    return 0;
}