Two friends stand at the 2 ends of a spiral matrix, with additional people in some cells in the middle. Each person can speak with a specific strength which indicates the maximum number of cells their voice can reach. Confirm if the friend at the beginning can pass a message to his friend at the end. The others in the middle who hear the message can repeat the message.

The message can be heard by multiple people in the middle if they are within reach of the previous person’s strength. More than one person can be in the same cell in which case you can pick the person with maximum reach.

Note that voice can only travel in the sequence of the spiral matrix.

Input Format

First line contains N, S and M, which are the size of the square maze(N*N), strength of the first friend’s voice and the number of people standing in the maze. Next M lines contain the position of each person in the maze and their voice strength.

1 ≤ N ≤ 103

1 ≤ M ≤ 105

Output Format

Print 'Yes' if the message could reach from the friend at the beginning to the friend at the end, else print 'No' (case-sensitive).

Input 1

4 5 4 --> Size is 4 * 4, first friend’s strength is 5, number of people is 4

0 3 2 --> First person’s position is 0,3 in the matrix. Their strength is 2

2 3 5

3 1 4

1 1 5

Output 1

Yes

Explanation 1

Y is the friend at the beginning. Z is the friend at the end. P are the other people.

0 1 2 3

0 Y(5) X X P1(3)

1 X P4(5) X X

2 X Z X P2(5)

3 X P3(4) X X

When Y speaks, voice will travel 5 cells through the following path and reach person1 and person2.

(0, 0)Y -> (0, 1) -> (0, 2) -> (0, 3)P1 -> (1, 3)

(2, 3)P2 -> (3, 3) -> (3, 2) -> (3, 1)P3 -> . . .

Following the spiral path, the message will be passed from P3 to P4 and then finally to Z.

My Solution :

#include

using namespace std;

int main()

{

int n, s, m;

cin >> n >> s >> m;

int maze[n][n];

for (int i = 0; i < n; ++i)

{

for (int j = 0; j < n; ++j)

maze[i][j] = 0;

}

maze[0][0] = s;

  

for (int i = 0; i < m; ++i)

{

int x, y, ts;

cin >> x >> y >> ts;

maze[x][y] = max(maze[x][y], ts);

}

int i, k = 0, l = 0;

int curStrength = 0;

bool possible = true;

while (k < m && l < n)

{

for (i = l; i < n; ++i)

{   

curStrength = max(curStrength, maze[k][i]);

curStrength--;

if(curStrength < 0) {

possible = false;

}

}

k++;

for (i = k; i < m; ++i)

{   

curStrength = max(curStrength, maze[i][n-1]);

curStrength--;

if(curStrength < 0) {

possible = false;

}

}

n--;

if (k < m)

{

for (i = n - 1; i >= l; --i)

{

curStrength = max(curStrength, maze[m-1][i]);

curStrength--;

if(curStrength < 0) {

possible = false;

}

}

m--;

}

if (l < n)

{

for (i = m - 1; i >= k; --i)

{

curStrength = max(curStrength, maze[i][l]);

curStrength--;

if(curStrength < 0) {

possible = false;

}

}

l++;

}

}

if(possible) cout << "Yes" << endl;

else cout << "No" << endl;

}

How to optimize this code for large matrix sizes?

Answer rating: 100% (QA)

include using namespace std int main int n s m cin n s m int mazenn for int ... View the full answer