C# - DFS - Code study - Simple and working
Nov. 20, 2020
Introduction
It is hard for me to understand the requirement under stress, my mock interview. I like to practice how to rephrase the problem.
Given the range of possible length of pattern, find how many variations to form pattern from 1-9 key screen 3 rows x 3 columns. The challenge is that every move should not cross unvisited digit in key screen.
Case study
1 2 3
4 5 6
7 8 9
example 1: pattern (2, 1, 3) - it is ok. second move, 1->3, 2 is already visited in first move.
example 2: pattern (1, 3, 2) - it is not allowed. First move 1 -> 3, 2 is not visited, so it is not a legal move.
The idea is to go over all possible lengths, and start from (0,0) or (0, 1) or (1, 1). It is true that all other three corners in 3 x 3 matrix is same as (0,0). Next it is true that all other three center node is same as (0, 1).
corner: 1, 3, 7, 9
middle: 2, 4, 6, 8
center: 5
public class Solution {
public int NumberOfPatterns(int m, int n) {
var row = 3;
var col = 3;
var minKeys = m;
var maxKeys = n;
var visited = new bool[row, col];
var result = 0;
for (int i = minKeys; i <= maxKeys; i++)
{
visited[0, 0] = true;
int topLeft = runDFS(visited, i - 1, 0, 0);
visited[0, 0] = false;
visited[0, 1] = true;
int middleLeft = runDFS(visited, i - 1, 0, 1);
visited[0, 1] = false;
visited[1, 1] = true;
int center = runDFS(visited, i - 1, 1, 1);
visited[1, 1] = false;
result += topLeft * 4 + middleLeft * 4 + center;
}
return result;
}
private int runDFS(bool[,] visited, int stepsLeft, int currentRow, int currentCol)
{
if (stepsLeft == 0)
{
return 1;
}
const int SIZE = 3;
var sum = 0;
for (int nextRow = 0; nextRow < SIZE; nextRow++)
{
for (int nextCol = 0; nextCol < SIZE; nextCol++)
{
if (visited[nextRow, nextCol])
{
continue;
}
if (!IsValid(currentRow, currentCol, nextRow, nextCol, visited))
{
continue;
}
visited[nextRow, nextCol] = true;
sum += runDFS(visited, stepsLeft - 1, nextRow, nextCol);
visited[nextRow, nextCol] = false;
}
}
return sum;
}
private bool IsValid(int startRow, int startCol, int nextRow, int nextCol, bool[,] visited)
{
var xDistance = Math.Abs(startRow - nextRow);
var yDistance = Math.Abs(startCol - nextCol);
if ((xDistance == 0 && yDistance == 2 && !visited[startRow, 1]) ||
(xDistance == 2 && yDistance == 0 && !visited[1, startCol]) ||
(xDistance == 2 && yDistance == 2 && !visited[1, 1]))
{
return false;
}
return true;
}
}
