Given a grid of dimensions n x n. A rat is placed at coordinates (0, 0) and wants to reach at coordinates (n-1, n-1). Find all possible paths that rat can take to travel from (0, 0) to (n-1, n-1). The directions in which rat can move are 'U' (up) , 'D' (down) , 'L' (left) , 'R' (right). The value 0 in grid denotes that the cell is blocked and rat cannot use that cell for travelling, whereas value 1 represents that rat can travel through the cell. If the cell (0, 0) has 0 value, then mouse cannot move to any other cell.
In a path no cell can be visited more than once. If there is no possible path then return empty vector.
Example:
// Input : n = 4 , grid = [ [1, 0, 0, 0] , [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1] ]
// Output : [ "DDRDRR" , "DRDDRR" ]
void func(vector<string> &ans, vector<vector<int>> &grid, int i, int j,
string path) {
if (i == grid.size() - 1 && j == grid.size() - 1) {
ans.push_back(path);
return;
}
if (grid[i][j] == 0) return;
grid[i][j] = 0;
if (i > 0) func(ans, grid, i - 1, j, path + "U");
if (j > 0) func(ans, grid, i, j - 1,path + "L");
if (i < grid.size() - 1) func(ans, grid, i + 1, j, path+"D");
if (j < grid.size() - 1) func(ans, grid, i, j + 1, path+"R");
grid[i][j] = 1;
}
vector<string> findPath(vector<vector<int>> &grid) {
vector<string> ans;
if (grid[0][0] == 0 || grid[grid.size() - 1][grid.size() - 1] == 0)
return ans;
func(ans, grid, 0, 0, "");
return ans;
}
You are given an m x n integer array grid where grid[i][j] could be: 1 representing the starting square. There is exactly one starting square. 2 representing the ending square. There is exactly one ending square. 0 representing empty squares we can walk over. -1 representing obstacles that we cannot walk over. Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.
int ans = 0;
int total;
int m;
int n;
void func(int i, int j, vector<vector<int>> &grid, int paths)
{
if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == -1)
return;
if (grid[i][j] == 2)
{
if (paths == total)
ans++;
return;
}
int prev = grid[i][j];
grid[i][j] = -1;
func(i + 1, j, grid, paths + 1);
func(i, j + 1, grid, paths + 1);
func(i - 1, j, grid, paths + 1);
func(i, j - 1, grid, paths + 1);
grid[i][j] = prev;
}
int uniquePathsIII(vector<vector<int>> &grid)
{
m = grid.size();
n = grid[0].size();
total = 1;
int si = 0, sj = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == 1)
{
si = i;
sj = j;
}
else if (grid[i][j] != -1)
total++;
}
}
func(si, sj, grid, 1);
return ans;
}
Given an integer M and an undirected graph with N vertices and E edges. The goal is to determine whether the graph can be coloured with a maximum of M colors so that no two of its adjacent vertices have the same colour applied to them. In this context, colouring a graph refers to giving each vertex a different colour. If the colouring of vertices is possible then return true, otherwise return false.
Examples:
// Input : N = 4 , M = 3 , E = 5 , Edges = [ (0, 1) , (1, 2) , (2, 3) , (3, 0) , (0, 2) ]
// Output : true
// Explanation : Consider the three colors to be red, green, blue.
// We can color the vertex 0 with red, vertex 1 with blue, vertex 2 with green, vertex 3 with blue.
// In this way we can color graph using 3 colors at most.
bool isPossible(int i, int node, vector<int> &colors, vector<int> adj[])
{
for (auto it : adj[node])
{
if (colors[it] == i) // adjacent node has the same color , cannot color
return false;
}
return true;
}
bool startColor(vector<int> adj[], vector<int> &colors, int m, int n, int node)
{
if (n == node)
return true;
for (int i = 1; i <= m; i++) // check all colors
{
if (isPossible(i, node, colors, adj))
{
colors[node] = i;
if (startColor(adj, colors, m, n, node + 1)) // check adjacent nodes with the current color
return true;
colors[node] = 0;
}
}
return false;
}
bool graphColoring(vector<vector<int>> &edges, int m, int n)
{
vector<int> adj[n];
for (int i = 0; i < edges.size(); i++)
{
adj[edges[i][0]].push_back(edges[i][1]);
adj[edges[i][1]].push_back(edges[i][0]);
}
vector<int> colors(n, -1);
return startColor(adj, colors, m, n, 0);
}