Challenge: Search in Sorted Matrix

Problem Statement

Implement a function that tells whether a given target is present in the sorted matrix or not. The sorted matrix has all elements sorted both row wise and column wise.

Input

A sorted matrix and the target that needs to be checked if it is present or not.

Output

Return 1 if the target is found, or 0 if the target is not found.

Sample Input

vector<vector<int>> matrix = { {10, 11, 12, 13}, {14, 15, 16, 17}, {27, 29, 30, 31}, {32, 33, 39, 80} };

target = 30

Sample Output

1