SDE - 1

You have been given a directed graph of 'V' vertices and 'E' edges.

Your task is to count the total number of ways to reach different nodes in the graph from the given source node ‘S’. A way is called as different from others if the destination node or used edges differ.

As the total number of such ways can be large, print the total ways modulo 10 ^ 9 + 7.

Note:

1. Include the source node as a destination also.
2. There are no cycles in the given graph.

You have a long fence in your backyard. The fence consists of 'N' sections, each of them made from a different material.

The fence is not painted yet, so you decide to hire 'Q' painters to paint it. The i-th painter will paint all the sections lying in the section range [Li, Ri].

Unfortunately, you are on a tight budget, so you decided to hire only 'Q' - 2 painters. Now, you want to maximise the number of painted sections in your fence, so you have to choose those 'Q' - 2 painters optimally.

Note:

A section is considered painted if at least one painter paints it.

You are given a matrix having ‘N’ rows and ‘M’ columns. Each cell of the matrix can only contain three values as given below:

-1 -> It denotes a wall or an obstacle

0  -> It denotes a gate

2^31 - 1 =  2147483647 ( INF ) -> An infinitely large value  denotes the empty room.

For each empty room (denoted by INF), you have to refill it with the distance to its nearest gate. If none of the gates is reachable from an empty room then the value ‘INF’ will remain as it is.

Example

For the matrix [[0,-1],[0,2147483647]] the updated matrix will be [[0,-1],[0,1]].

Note

The distance between two cells having their coordinates (x1,y1) and (x2,y2) are abs(x2-x1) + abs(y2-y1).

You are given a list of “N” strings A. Your task is to check whether you can form a given target string using a combination of one or more strings of A.

Note :

You can use any string of A multiple times.

Examples :

A =[“coding”, ”ninjas”, “is”, “awesome”]  target = “codingninjas”
Ans = true as we use “coding” and “ninjas” to form “codingninjas”

You are given an array/list 'asteroids' representing asteroids in a row.

For each element of the given array, its absolute value denotes the size of that asteroid, and its sign denotes the direction it moves in(+ve meaning right and -ve meaning left).

An asteroid with a weight of 0 denotes a massless asteroid that moves in the right direction.

All asteroids are moving at the same speed. Whenever two asteroids collide, the smaller asteroid gets destroyed.

If both asteroids are the same size, then both asteroids get destroyed. Two asteroids moving in the same direction never collide.

You are supposed to find the state of the asteroids after all collisions.

Example :

Input: ‘asteroids’ = [3,-2,4]

Output: [3, 4]

Explanation: The first asteroid will destroy the second asteroid. Hence, after the collision, the state of the asteroids will be [3,4].

Note:

You don’t need to print anything. Just implement the given function.