-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathCoordinates of the last cell in a Matrix on which performing given operations exits from the Matrix.cpp
91 lines (74 loc) · 2.04 KB
/
Coordinates of the last cell in a Matrix on which performing given operations exits from the Matrix.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
class Solution{
public:
bool issafe(int m, int n, int i, int j)
{
// Cases for invalid cells
if (i < 0)
return false;
if (j < 0)
return false;
if (i >= m)
return false;
if (j >= n)
return false;
// Return true if valid
return true;
}
// Function to find indices of cells
// of a matrix from which traversal
// leads to out of the matrix
pair<int,int> endPoints(vector<vector<int>> arr){
// Starting from cell (0, 0),
// traverse in right direction
int m = arr.size();
int n = arr[0].size();
int i = 0;
int j = 0;
int current_i = 0;
int current_j = 0;
char current_d = 'r';
// Stores direction changes
map<char,char> rcd = {{'l', 'u'},{'u', 'r'},
{'r', 'd'},
{'d', 'l'}};
// Iterate until the current cell
// exceeds beyond the matrix
while (issafe(m, n, i, j)){
// Current index
current_i = i;
current_j = j;
// If the current cell is 1
if (arr[i][j] == 1){
char move_in = rcd[current_d];
// Update arr[i][j] = 0
arr[i][j] = 0;
// Update indices according
// to the direction
if (move_in == 'u')
i -= 1;
else if(move_in == 'd')
i += 1;
else if(move_in == 'l')
j -= 1;
else if(move_in == 'r')
j += 1;
current_d = move_in;
}
// Otherwise
else{
// Update indices according
// to the direction
if (current_d == 'u')
i -= 1;
else if(current_d == 'd')
i += 1;
else if(current_d == 'l')
j -= 1;
else if(current_d == 'r')
j += 1;
}
}
// The exit cooridnates
return {current_i, current_j};
}
};