{"id":772,"date":"2025-07-22T15:08:29","date_gmt":"2025-07-22T09:38:29","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=772"},"modified":"2025-07-22T15:08:30","modified_gmt":"2025-07-22T09:38:30","slug":"rat-in-a-maze-problem","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/rat-in-a-maze-problem\/","title":{"rendered":"Rat in a Maze Problem &#8211; I | GFG Practice | 2 different solutions"},"content":{"rendered":"\n<p>Consider a rat placed at position (0, 0) in an&nbsp;<strong>n x n<\/strong>&nbsp;square matrix&nbsp;<code><strong>mat[][]<\/strong><\/code>. The rat&#8217;s goal is to reach the destination at position (n-1, n-1). The rat can move in four possible directions:&nbsp;<strong>&#8216;U'(up)<\/strong>,&nbsp;<strong>&#8216;D'(down)<\/strong>,&nbsp;<strong>&#8216;L&#8217; (left)<\/strong>,&nbsp;<strong>&#8216;R&#8217; (right)<\/strong>.<\/p>\n\n\n\n<p>The matrix contains only two possible values:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>0<\/code>: A blocked cell through which the rat\u00a0<strong>cannot<\/strong>\u00a0travel.<\/li>\n\n\n\n<li><code>1<\/code>: A free cell that the rat\u00a0<strong>can<\/strong>\u00a0pass through.<\/li>\n<\/ul>\n\n\n\n<p>Your task is to find&nbsp;<strong>all possible paths<\/strong>&nbsp;the rat can take to reach the destination, starting from (0, 0) and ending at (n-1, n-1), under the condition that the rat cannot&nbsp;<strong>revisit<\/strong>&nbsp;any cell along the same path. Furthermore, the rat can only move to adjacent cells that are within the bounds of the matrix and not blocked.<br>If no path exists, return an&nbsp;<strong>empty list<\/strong><strong>.<\/strong><\/p>\n\n\n\n<p><strong>Note:<\/strong>&nbsp;Return the final result vector in&nbsp;<strong>lexicographically smallest order<\/strong>.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/www.geeksforgeeks.org\/problems\/rat-in-a-maze-problem\/1\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input<\/strong>: mat[][] = [[1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1]]\n<strong>Output: <\/strong>[\"DDRDRR\", \"DRDDRR\"]\n<strong>Explanation<\/strong>: The rat can reach the destination at (3, 3) from (0, 0) by two paths - DRDDRR and DDRDRR, when printed in sorted order we get DDRDRR DRDDRR.<\/pre>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input<\/strong>: mat[][] = [[1, 0], [1, 0]]<br><strong>Output: <\/strong>[]<br><strong>Explanation<\/strong>: No path exists as the destination cell is blocked.<\/pre>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input<\/strong>: mat = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]\n<strong>Output: <\/strong>[\"DDRR\", \"RRDD\"]\n<strong>Explanation<\/strong>: The rat has two possible paths to reach the destination: 1. \"DDRR\" 2. \"RRDD\", These are returned in lexicographically sorted order.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><br>2 \u2264 mat.size() \u2264 5<br>0 \u2264 mat[i][j] \u2264 1<\/p>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-21360fb3-ac2e-47d5-8dfc-a5c682178edc\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/rat-in-a-maze-problem\/#0-solution-1-brute-force-approach-explicit-direction-handling\" style=\"\">Solution 1: Brute Force Approach (Explicit Direction Handling)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/rat-in-a-maze-problem\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/rat-in-a-maze-problem\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/rat-in-a-maze-problem\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/rat-in-a-maze-problem\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/rat-in-a-maze-problem\/#5-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/rat-in-a-maze-problem\/#6-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/rat-in-a-maze-problem\/#7-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/rat-in-a-maze-problem\/#8-solution-2-optimal-approach-direction-arrays-for-clean-code\" style=\"\">Solution 2: Optimal Approach (Direction Arrays for Clean Code)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/rat-in-a-maze-problem\/#9-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/rat-in-a-maze-problem\/#10-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/rat-in-a-maze-problem\/#11-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/rat-in-a-maze-problem\/#12-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/rat-in-a-maze-problem\/#13-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/rat-in-a-maze-problem\/#14-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/rat-in-a-maze-problem\/#15-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/rat-in-a-maze-problem\/#16-summary\" style=\"\">Summary<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-solution-1-brute-force-approach-explicit-direction-handling\">Solution 1: Brute Force Approach (Explicit Direction Handling)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Think of this like helping a rat navigate through a maze by trying every possible route! The brute force approach explicitly handles each of the four possible directions (Down, Left, Right, Up) with separate if-conditions. For each direction, we check if it&#8217;s valid (within bounds, not visited, and not blocked), then recursively explore that path. It&#8217;s like being a maze solver who methodically checks &#8220;Can I go down? Can I go left? Can I go right? Can I go up?&#8221; at every junction, trying each valid option one by one.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Explicit Direction Checks<\/strong>: Use separate if-statements for each direction (D, L, R, U).<\/li>\n\n\n\n<li><strong>Boundary &amp; Validity Checks<\/strong>: For each direction, check:\n<ul class=\"wp-block-list\">\n<li>Within maze boundaries<\/li>\n\n\n\n<li>Cell not already visited (to avoid cycles)<\/li>\n\n\n\n<li>Cell is open (value = 1)<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Backtracking Pattern<\/strong>:\n<ul class=\"wp-block-list\">\n<li>Mark current cell as visited<\/li>\n\n\n\n<li>Recursively explore the direction<\/li>\n\n\n\n<li>Unmark cell (backtrack) when returning<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Path Building<\/strong>: Build path string by appending direction characters (&#8220;D&#8221;, &#8220;L&#8221;, &#8220;R&#8221;, &#8220;U&#8221;).<\/li>\n\n\n\n<li><strong>Base Case<\/strong>: When rat reaches (N-1, N-1), add the complete path to results.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"def findPathHelper(\n    i: int, j: int, a: List[List[int]], n: int, \n    ans: List[str], move: str, vis: List[List[int]]\n):\n    # Base case: reached destination\n    if i == n - 1 and j == n - 1:\n        ans.append(move)\n        return\n\n    # Try going downward (i+1, j)\n    if i + 1 &lt; n and not vis[i + 1][j] and a[i + 1][j] == 1:\n        vis[i][j] = 1  # Mark current cell as visited\n        findPathHelper(i + 1, j, a, n, ans, move + &quot;D&quot;, vis)\n        vis[i][j] = 0  # Backtrack: unmark current cell\n\n    # Try going left (i, j-1)\n    if j - 1 &gt;= 0 and not vis[i][j - 1] and a[i][j - 1] == 1:\n        vis[i][j] = 1\n        findPathHelper(i, j - 1, a, n, ans, move + &quot;L&quot;, vis)\n        vis[i][j] = 0\n\n    # Try going right (i, j+1)\n    if j + 1 &lt; n and not vis[i][j + 1] and a[i][j + 1] == 1:\n        vis[i][j] = 1\n        findPathHelper(i, j + 1, a, n, ans, move + &quot;R&quot;, vis)\n        vis[i][j] = 0\n\n    # Try going upward (i-1, j)\n    if i - 1 &gt;= 0 and not vis[i - 1][j] and a[i - 1][j] == 1:\n        vis[i][j] = 1\n        findPathHelper(i - 1, j, a, n, ans, move + &quot;U&quot;, vis)\n        vis[i][j] = 0\n\ndef ratMaze(matrix: List[List[int]]) -&gt; List[str]:\n    n = len(matrix)\n    ans = []\n    vis = [[0 for _ in range(n)] for _ in range(n)]  # Visited array\n    \n    # Only start if source cell is open\n    if matrix[0][0] == 1:\n        findPathHelper(0, 0, matrix, n, ans, &quot;&quot;, vis)\n    return ans\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">findPathHelper<\/span><span style=\"color: #D4D4D4\">(<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #9CDCFE\">i<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">j<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">a<\/span><span style=\"color: #D4D4D4\">: List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]], <\/span><span style=\"color: #9CDCFE\">n<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">, <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #9CDCFE\">ans<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">], <\/span><span style=\"color: #9CDCFE\">move<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">vis<\/span><span style=\"color: #D4D4D4\">: List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Base case: reached destination<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i == n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> j == n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        ans.append(move)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Try going downward (i+1, j)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> &lt; n <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> vis[i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][j] <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> a[i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][j] == <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        vis[i][j] = <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Mark current cell as visited<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        findPathHelper(i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, j, a, n, ans, move + <\/span><span style=\"color: #CE9178\">&quot;D&quot;<\/span><span style=\"color: #D4D4D4\">, vis)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        vis[i][j] = <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Backtrack: unmark current cell<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Try going left (i, j-1)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> j - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> &gt;= <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> vis[i][j - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> a[i][j - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] == <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        vis[i][j] = <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        findPathHelper(i, j - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, a, n, ans, move + <\/span><span style=\"color: #CE9178\">&quot;L&quot;<\/span><span style=\"color: #D4D4D4\">, vis)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        vis[i][j] = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Try going right (i, j+1)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> j + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> &lt; n <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> vis[i][j + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> a[i][j + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] == <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        vis[i][j] = <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        findPathHelper(i, j + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, a, n, ans, move + <\/span><span style=\"color: #CE9178\">&quot;R&quot;<\/span><span style=\"color: #D4D4D4\">, vis)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        vis[i][j] = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Try going upward (i-1, j)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> &gt;= <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> vis[i - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][j] <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> a[i - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][j] == <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        vis[i][j] = <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        findPathHelper(i - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, j, a, n, ans, move + <\/span><span style=\"color: #CE9178\">&quot;U&quot;<\/span><span style=\"color: #D4D4D4\">, vis)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        vis[i][j] = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">ratMaze<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">matrix<\/span><span style=\"color: #D4D4D4\">: List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]]) -&gt; List[<\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(matrix)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    ans = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    vis = [[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n)] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n)]  <\/span><span style=\"color: #6A9955\"># Visited array<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Only start if source cell is open<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> matrix[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] == <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        findPathHelper(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, matrix, n, ans, <\/span><span style=\"color: #CE9178\">&quot;&quot;<\/span><span style=\"color: #D4D4D4\">, vis)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> ans<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>This brute force solution explicitly handles each direction with separate if-conditions. Each direction check follows the same pattern: validate boundaries, check if cell is unvisited and open, then mark current cell as visited, recursively explore, and backtrack by unmarking. The&nbsp;<code>move<\/code>&nbsp;string accumulates the path taken so far, and when we reach the destination, we add it to our results. The visited array prevents infinite loops by ensuring we don&#8217;t revisit cells in the current path.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through:\u00a0<code>matrix = [[1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1]]<\/code><\/p>\n\n\n\n<div class=\"wp-block-merpress-mermaidjs diagram-source-mermaid\"><pre class=\"mermaid\">graph TD\n    Root[\"findPathHelper(0,0, move='', vis=all 0)&lt;br\/>Matrix: [[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]]&lt;br\/>Start at (0,0), target (3,3)\"]\n    \n    %% Level 0: From (0,0), check 4 directions\n    Root --- A[\"Try Down to (1,0)&lt;br\/>Check: i+1=1 &lt; 4 \u2713, vis[1][0]=0 \u2713, mat[1][0]=1 \u2713&lt;br\/>Mark vis[0][0]=1, move='D'&lt;br\/>Recurse to (1,0)\"]\n    Root --- B[\"Try Left: j-1=-1 &lt; 0 \u274c&lt;br\/>Out of bounds\"]\n    Root --- C[\"Try Right to (0,1)&lt;br\/>Check: j+1=1 &lt; 4 \u2713, vis[0][1]=0 \u2713, mat[0][1]=0 \u274c&lt;br\/>Blocked cell\"]\n    Root --- D[\"Try Up: i-1=-1 &lt; 0 \u274c&lt;br\/>Out of bounds\"]\n    \n    %% Level 1: From (1,0), check 4 directions  \n    A --- A1[\"Try Down to (2,0)&lt;br\/>Check: mat[2][0]=1 \u2713, not visited \u2713&lt;br\/>Mark vis[1][0]=1, move='DD'&lt;br\/>Recurse to (2,0)\"]\n    A --- A2[\"Try Left: j-1=-1 &lt; 0 \u274c&lt;br\/>Out of bounds\"]\n    A --- A3[\"Try Right to (1,1)&lt;br\/>Check: mat[1][1]=1 \u2713, not visited \u2713&lt;br\/>Mark vis[1][0]=1, move='DR'&lt;br\/>Recurse to (1,1)\"]\n    A --- A4[\"Try Up to (0,0)&lt;br\/>Check: mat[0][0]=1 \u2713, but vis[0][0]=1 \u274c&lt;br\/>Already visited\"]\n    \n    %% Level 2: From (2,0), check 4 directions\n    A1 --- A1a[\"Try Down: mat[3][0]=0 \u274c&lt;br\/>Blocked cell\"]\n    A1 --- A1b[\"Try Left: j-1=-1 &lt; 0 \u274c&lt;br\/>Out of bounds\"]\n    A1 --- A1c[\"Try Right to (2,1)&lt;br\/>Check: mat[2][1]=1 \u2713, not visited \u2713&lt;br\/>Mark vis[2][0]=1, move='DDR'&lt;br\/>Recurse to (2,1)\"]\n    A1 --- A1d[\"Try Up to (1,0)&lt;br\/>vis[1][0]=1 \u274c&lt;br\/>Already visited\"]\n    \n    %% Level 2: From (1,1), check 4 directions  \n    A3 --- A3a[\"Try Down to (2,1)&lt;br\/>Check: mat[2][1]=1 \u2713, not visited \u2713&lt;br\/>Mark vis[1][1]=1, move='DRD'&lt;br\/>Recurse to (2,1)\"]\n    A3 --- A3b[\"Try Left to (1,0)&lt;br\/>vis[1][0]=1 \u274c&lt;br\/>Already visited\"]\n    A3 --- A3c[\"Try Right to (1,2)&lt;br\/>mat[1][2]=0 \u274c&lt;br\/>Blocked cell\"]\n    A3 --- A3d[\"Try Up to (0,1)&lt;br\/>mat[0][1]=0 \u274c&lt;br\/>Blocked cell\"]\n    \n    %% Level 3: From (2,1) via path DD, check 4 directions\n    A1c --- A1c1[\"Try Down to (3,1)&lt;br\/>Check: mat[3][1]=1 \u2713, not visited \u2713&lt;br\/>Mark vis[2][1]=1, move='DDRD'&lt;br\/>Recurse to (3,1)\"]\n    A1c --- A1c2[\"Try Left to (2,0)&lt;br\/>vis[2][0]=1 \u274c&lt;br\/>Already visited\"]\n    A1c --- A1c3[\"Try Right to (2,2)&lt;br\/>mat[2][2]=0 \u274c&lt;br\/>Blocked cell\"]\n    A1c --- A1c4[\"Try Up to (1,1)&lt;br\/>mat[1][1]=1 \u2713, not visited \u2713&lt;br\/>Mark vis[2][1]=1, move='DDRU'&lt;br\/>Recurse to (1,1)\"]\n    \n    %% Level 3: From (2,1) via path DR, check 4 directions\n    A3a --- A3a1[\"Try Down to (3,1)&lt;br\/>Check: mat[3][1]=1 \u2713, not visited \u2713&lt;br\/>Mark vis[2][1]=1, move='DRDD'&lt;br\/>Recurse to (3,1)\"]\n    A3a --- A3a2[\"Try Left to (2,0)&lt;br\/>mat[2][0]=1 \u2713, not visited \u2713&lt;br\/>Mark vis[2][1]=1, move='DRDL'&lt;br\/>Recurse to (2,0)\"]\n    A3a --- A3a3[\"Try Right to (2,2)&lt;br\/>mat[2][2]=0 \u274c&lt;br\/>Blocked cell\"]\n    A3a --- A3a4[\"Try Up to (1,1)&lt;br\/>vis[1][1]=1 \u274c&lt;br\/>Already visited\"]\n    \n    %% Level 4: From (3,1) via path DDRD\n    A1c1 --- A1c1a[\"Try Down: i+1=4 >= 4 \u274c&lt;br\/>Out of bounds\"]\n    A1c1 --- A1c1b[\"Try Left to (3,0)&lt;br\/>mat[3][0]=0 \u274c&lt;br\/>Blocked cell\"]\n    A1c1 --- A1c1c[\"Try Right to (3,2)&lt;br\/>Check: mat[3][2]=1 \u2713, not visited \u2713&lt;br\/>Mark vis[3][1]=1, move='DDRDR'&lt;br\/>Recurse to (3,2)\"]\n    A1c1 --- A1c1d[\"Try Up to (2,1)&lt;br\/>vis[2][1]=1 \u274c&lt;br\/>Already visited\"]\n    \n    %% Level 4: From (3,1) via path DRDD\n    A3a1 --- A3a1a[\"Try Down: i+1=4 >= 4 \u274c&lt;br\/>Out of bounds\"]\n    A3a1 --- A3a1b[\"Try Left to (3,0)&lt;br\/>mat[3][0]=0 \u274c&lt;br\/>Blocked cell\"]\n    A3a1 --- A3a1c[\"Try Right to (3,2)&lt;br\/>Check: mat[3][2]=1 \u2713, not visited \u2713&lt;br\/>Mark vis[3][1]=1, move='DRDDR'&lt;br\/>Recurse to (3,2)\"]\n    A3a1 --- A3a1d[\"Try Up to (2,1)&lt;br\/>vis[2][1]=1 \u274c&lt;br\/>Already visited\"]\n    \n    %% Level 5: From (3,2) via path DDRDR\n    A1c1c --- A1c1c1[\"Try Down: i+1=4 >= 4 \u274c&lt;br\/>Out of bounds\"]\n    A1c1c --- A1c1c2[\"Try Left to (3,1)&lt;br\/>vis[3][1]=1 \u274c&lt;br\/>Already visited\"]\n    A1c1c --- A1c1c3[\"Try Right to (3,3)&lt;br\/>Check: mat[3][3]=1 \u2713, not visited \u2713&lt;br\/>i=3, j=3 == n-1=3 \u2713&lt;br\/>Found destination!&lt;br\/>move='DDRDDR'\"]\n    A1c1c --- A1c1c4[\"Try Up to (2,2)&lt;br\/>mat[2][2]=0 \u274c&lt;br\/>Blocked cell\"]\n    \n    %% Level 5: From (3,2) via path DRDDR  \n    A3a1c --- A3a1c1[\"Try Down: i+1=4 >= 4 \u274c&lt;br\/>Out of bounds\"]\n    A3a1c --- A3a1c2[\"Try Left to (3,1)&lt;br\/>vis[3][1]=1 \u274c&lt;br\/>Already visited\"]\n    A3a1c --- A3a1c3[\"Try Right to (3,3)&lt;br\/>Check: mat[3][3]=1 \u2713, not visited \u2713&lt;br\/>i=3, j=3 == n-1=3 \u2713&lt;br\/>Found destination!&lt;br\/>move='DRDDRR'\"]\n    A3a1c --- A3a1c4[\"Try Up to (2,2)&lt;br\/>mat[2][2]=0 \u274c&lt;br\/>Blocked cell\"]\n    \n    %% Success cases\n    A1c1c3 --- Success1[\"\u2705 Add 'DDRDDR' to result&lt;br\/>Backtrack and unmark vis arrays\"]\n    A3a1c3 --- Success2[\"\u2705 Add 'DRDDRR' to result&lt;br\/>Backtrack and unmark vis arrays\"]\n    \n    %% Final result\n    Success1 --- Final[\"Final Result: ['DDRDDR', 'DRDDRR']\"]\n    Success2 --- Final\n\n    %% Styling\n    style Success1 fill:#90EE90\n    style Success2 fill:#90EE90\n    style Final fill:#90EE90\n    \n    style B fill:#FFB6C1\n    style C fill:#FFB6C1\n    style D fill:#FFB6C1\n    style A2 fill:#FFB6C1\n    style A4 fill:#FFB6C1\n    style A1a fill:#FFB6C1\n    style A1b fill:#FFB6C1\n    style A1d fill:#FFB6C1\n    style A3b fill:#FFB6C1\n    style A3c fill:#FFB6C1\n    style A3d fill:#FFB6C1\n    \n    style A1c1c3 fill:#87CEEB\n    style A3a1c fill:#87CEEB\n    style A1c1 fill:#87CEEB\n    style A3a1 fill:#87CEEB\n    \n    style Root fill:#E6E6FA\n<\/pre><\/div>\n\n\n\n<p>For detailed dry run [<strong><a href=\"https:\/\/mermaid.live\/edit#pako:eNrFmM1u4zYQx1-FVbHIBpVTkZSdWFgv4Fg2ekjRQrt7qe0DI9G2NrJkSHS6aZBjb731un25fZKS-qQ-7bgJmgCBxOEMZ_j7DynkUbEDhyqGsg7JbgM-mgsf8B8rCNh8oaxc3_mVsM1P1NvR8K2mairYBvd0dHamgns3GhHPA9r5u9vwx_c_Exa6Xwwwn0NVTNSWKn8SzzB_EmP8Xfwul7HXB0ZCBggDIvi5CvjrmvI3rOLzhbJMskn-vnkDbug95QsaYBYG28zF3lD7DujAcUNqMzfwo6IG0Ov1wJhX8jF8AGbwuw9YAN7yVJKcJ8LVAO4PcATBOx7j29e_48LmcDnXliMtGdgSlg5AMZCWG97FM7XEkG2MeRabLWrvw4jmy-W15Fldp1nd0BUzwOceHPVEDnzJf_6KQ_yyZyBYgdtg7ztR3X-S-lvuesPidfjOlsr6XC-LJwtLZeUD6aLXXmDfUQfY1PPqa5rpmp92fNOOzbhCD2b0YAu9zGOcwINVeqhCT5SBCjoq8Hm2vFiX8TpquGAFVwMvJPNKs0Cn0Uq9cY0VrLBKJQZPK8JqEh2sFaHn-FK91DdSkzfyds9kiee1jr2QEuchy6-NNMpIo84-HcMUNJFIJ9ngrAu71Jn7357IKPO3a5RQAyV0NCVUlZrVpDUZU5aJUwaVn1cS-5NhCGF0th1ONUvqjfdfdiNVd6FZ89BuZInIXE_fjzyc3dCMKImXdiE6rLksmFNtKVhEOupsrWDCRc_Ac14DATt-_wLT7OofOxNw7azEDcjwcwQMywJuYIbLCs5zQVVqSKaGjqVWBMQN7SlxQ0dxK8Lp1R6DJQ2cvEWfDpzFRwK3OoBjkrXoKwO3zIPAi1zagT_vhq4ncXPoji6SeBGRFOHaRCIdaM89iPUMOK50uGXmGs1vpMqdKD5UdfB-JD7pDtxpUoza-YllMEfesVK8-gGKsz0uqw4dBxzXjxmrSXbovDmfyhmMZEjoZSHxhsg1AvMmPBWSHOMlIMnxXhuSZR6GJOfzCpD6BSRU6SSrkElxOZaux2c2kxQF1UlJteAja6kExQ24cBMu3InLHWEVfB5hMBoBn38A49wyEzUBh0bM9Ym4TL5LxJW3HMfZlpxeZffcE_VIcCKJ4jOUZCmIJ3h6i0lRXghdOej_jE5smoyunNzLofuwt20aRcAmEY0kmSRfwqlVYPr29U8wdhyQqUosHNJo77FkFWLfsZD_AYRXtfe36QkDSBiShwq6UnBUCp7UfWLwvKoZ31IvjZAMZpXEK8dmvmwyzYqnGWCelabmeSzz0Fmyhf_CLzaRPXiuv07eI_5Ci_VWrucZ3w-16XSoNUxArROS5OpWec51ap_NrgcTKFsmrRaz1TJG7Sa93QRJh-22w-a023CHH7Y7bE0xy6vG4k4mXV1OptPrcgDRZ61W8X3S5dpglKfE_3FLpkwH08FsvPAVVVmHrqMYLNxTVdnScEvEq_IoHBcK29AtXSgGf3Toigg9Kwv_ibvtiP9bEGwzzzDYrzeKsSJexN_2O4cwarpkHZJtPhpS36HhhB88TDGwBlEcRTEelS-K0dO1C13HuA8RvtTQUMeq8sCHIepfDLX-EGlXfXSp6YP-k6r8Ea8MLwawPxhe9XmsPtR01H_6FyVWzfM\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Click here<\/span><\/mark><\/a><\/strong>]<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>\u00a0O(4^(N\u00d7N)) &#8211; In worst case, we explore 4 directions at each of N\u00d7N cells<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>\u00a0O(N\u00d7N) &#8211; Visited array plus maximum recursion depth of N\u00d7N<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"7-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This approach is like having a very methodical rat that at every junction says &#8220;Let me try going down first, then left, then right, then up&#8221; and carefully explores each direction one by one. It&#8217;s straightforward but involves a lot of repetitive code for each direction.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"8-solution-2-optimal-approach-direction-arrays-for-clean-code\">Solution 2: Optimal Approach (Direction Arrays for Clean Code)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-intuition\">Intuition<\/h3>\n\n\n\n<p>Instead of writing separate code for each direction, why not be smart and use arrays to represent all directions uniformly? This is like having a compass that points to all four directions &#8211; we can loop through the directions instead of hardcoding each one. The key insight is that all four directions follow the same pattern: check validity, mark visited, recurse, backtrack. By using direction arrays (di, dj) and a direction string &#8220;DLRU&#8221;, we can handle all directions in a single loop, making the code much cleaner and more maintainable.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Direction Arrays<\/strong>: Use\u00a0<code>di = [+1, 0, 0, -1]<\/code>\u00a0and\u00a0<code>dj = [0, -1, +1, 0]<\/code>\u00a0to represent direction offsets.<\/li>\n\n\n\n<li><strong>Direction String<\/strong>: Use\u00a0<code>\"DLRU\"<\/code>\u00a0to map array indices to direction characters.<\/li>\n\n\n\n<li><strong>Unified Loop<\/strong>: Single for-loop to try all 4 directions instead of 4 separate if-statements.<\/li>\n\n\n\n<li><strong>Same Logic<\/strong>: Each iteration follows the same pattern: calculate next position, validate, recurse, backtrack.<\/li>\n\n\n\n<li><strong>Cleaner Code<\/strong>: Eliminates code duplication while maintaining the same algorithmic approach.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"def solve(\n    i: int, j: int, a: List[List[int]], n: int,\n    ans: List[str], move: str, vis: List[List[int]],\n    di: List[int], dj: List[int]\n):\n    # Base case: reached destination\n    if i == n - 1 and j == n - 1:\n        ans.append(move)\n        return\n    \n    dir = &quot;DLRU&quot;  # Direction characters corresponding to di, dj arrays\n    \n    # Try all 4 directions in a loop\n    for ind in range(4):\n        nexti = i + di[ind]  # Calculate next row\n        nextj = j + dj[ind]  # Calculate next column\n        \n        # Check if next position is valid\n        if (\n            nexti &gt;= 0 and nextj &gt;= 0 and          # Within upper bounds\n            nexti &lt; n and nextj &lt; n and            # Within lower bounds  \n            not vis[nexti][nextj] and              # Not visited\n            a[nexti][nextj] == 1                   # Open cell\n        ):\n            vis[i][j] = 1  # Mark current cell as visited\n            solve(nexti, nextj, a, n, ans, move + dir[ind], vis, di, dj)\n            vis[i][j] = 0  # Backtrack: unmark current cell\n\ndef ratMaze(matrix: List[List[int]]) -&gt; List[str]:\n    n = len(matrix)\n    ans = []\n    vis = [[0 for _ in range(n)] for _ in range(n)]\n    \n    # Direction arrays: Down, Left, Right, Up\n    di = [+1, 0, 0, -1]  # Row offsets\n    dj = [0, -1, +1, 0]  # Column offsets\n    \n    # Only start if source cell is open\n    if matrix[0][0] == 1:\n        solve(0, 0, matrix, n, ans, &quot;&quot;, vis, di, dj)\n    return ans\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">solve<\/span><span style=\"color: #D4D4D4\">(<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #9CDCFE\">i<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">j<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">a<\/span><span style=\"color: #D4D4D4\">: List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]], <\/span><span style=\"color: #9CDCFE\">n<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">,<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #9CDCFE\">ans<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">], <\/span><span style=\"color: #9CDCFE\">move<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">vis<\/span><span style=\"color: #D4D4D4\">: List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]],<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #9CDCFE\">di<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">], <\/span><span style=\"color: #9CDCFE\">dj<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Base case: reached destination<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i == n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> j == n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        ans.append(move)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #DCDCAA\">dir<\/span><span style=\"color: #D4D4D4\"> = <\/span><span style=\"color: #CE9178\">&quot;DLRU&quot;<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Direction characters corresponding to di, dj arrays<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Try all 4 directions in a loop<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> ind <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">4<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        nexti = i + di[ind]  <\/span><span style=\"color: #6A9955\"># Calculate next row<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        nextj = j + dj[ind]  <\/span><span style=\"color: #6A9955\"># Calculate next column<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Check if next position is valid<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> (<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            nexti &gt;= <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> nextj &gt;= <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\">          <\/span><span style=\"color: #6A9955\"># Within upper bounds<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            nexti &lt; n <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> nextj &lt; n <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Within lower bounds  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> vis[nexti][nextj] <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\">              <\/span><span style=\"color: #6A9955\"># Not visited<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            a[nexti][nextj] == <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">                   <\/span><span style=\"color: #6A9955\"># Open cell<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        ):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            vis[i][j] = <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Mark current cell as visited<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            solve(nexti, nextj, a, n, ans, move + <\/span><span style=\"color: #DCDCAA\">dir<\/span><span style=\"color: #D4D4D4\">[ind], vis, di, dj)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            vis[i][j] = <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Backtrack: unmark current cell<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">ratMaze<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">matrix<\/span><span style=\"color: #D4D4D4\">: List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]]) -&gt; List[<\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(matrix)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    ans = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    vis = [[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n)] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Direction arrays: Down, Left, Right, Up<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    di = [+<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]  <\/span><span style=\"color: #6A9955\"># Row offsets<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    dj = [<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, +<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">]  <\/span><span style=\"color: #6A9955\"># Column offsets<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Only start if source cell is open<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> matrix[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] == <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        solve(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, matrix, n, ans, <\/span><span style=\"color: #CE9178\">&quot;&quot;<\/span><span style=\"color: #D4D4D4\">, vis, di, dj)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> ans<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>This optimal solution uses direction arrays to eliminate code duplication. The&nbsp;<code>di<\/code>&nbsp;and&nbsp;<code>dj<\/code>&nbsp;arrays represent row and column offsets for each direction: Down (+1,0), Left (0,-1), Right (0,+1), Up (-1,0). The string&nbsp;<code>\"DLRU\"<\/code>&nbsp;maps these array indices to their corresponding direction characters. Instead of four separate if-conditions, we use a single loop that tries each direction systematically. The validation logic remains the same, but now it&#8217;s centralized in one place, making the code more maintainable and less error-prone.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through:\u00a0<code>matrix = [[1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1]]<\/code><\/p>\n\n\n\n<div class=\"wp-block-merpress-mermaidjs diagram-source-mermaid\"><pre class=\"mermaid\">graph TD\n    Root[\"solve(0,0, move='', vis=all 0)&lt;br\/>Matrix: [[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]]&lt;br\/>di=[+1,0,0,-1], dj=[0,-1,+1,0], dir='DLRU'&lt;br\/>Start at (0,0), target (3,3)\"]\n    \n    %% Level 0: From (0,0), loop through 4 directions (ind=0,1,2,3)\n    Root --- A[\"ind=0: D (Down)&lt;br\/>nexti=0+1=1, nextj=0+0=0&lt;br\/>Check: (1,0) in bounds \u2713, vis[1][0]=0 \u2713, mat[1][0]=1 \u2713&lt;br\/>Mark vis[0][0]=1, move='D'&lt;br\/>Recurse to (1,0)\"]\n    Root --- B[\"ind=1: L (Left)&lt;br\/>nexti=0+0=0, nextj=0-1=-1&lt;br\/>Check: nextj=-1 &lt; 0 \u274c&lt;br\/>Out of bounds\"]\n    Root --- C[\"ind=2: R (Right)&lt;br\/>nexti=0+0=0, nextj=0+1=1&lt;br\/>Check: (0,1) in bounds \u2713, vis[0][1]=0 \u2713, mat[0][1]=0 \u274c&lt;br\/>Blocked cell\"]\n    Root --- D[\"ind=3: U (Up)&lt;br\/>nexti=0-1=-1, nextj=0+0=0&lt;br\/>Check: nexti=-1 &lt; 0 \u274c&lt;br\/>Out of bounds\"]\n    \n    %% Level 1: From (1,0), loop through 4 directions\n    A --- A1[\"ind=0: D (Down)&lt;br\/>nexti=1+1=2, nextj=0+0=0&lt;br\/>Check: (2,0) valid, mat[2][0]=1 \u2713&lt;br\/>Mark vis[1][0]=1, move='DD'&lt;br\/>Recurse to (2,0)\"]\n    A --- A2[\"ind=1: L (Left)&lt;br\/>nexti=1+0=1, nextj=0-1=-1&lt;br\/>Check: nextj=-1 &lt; 0 \u274c&lt;br\/>Out of bounds\"]\n    A --- A3[\"ind=2: R (Right)&lt;br\/>nexti=1+0=1, nextj=0+1=1&lt;br\/>Check: (1,1) valid, mat[1][1]=1 \u2713&lt;br\/>Mark vis[1][0]=1, move='DR'&lt;br\/>Recurse to (1,1)\"]\n    A --- A4[\"ind=3: U (Up)&lt;br\/>nexti=1-1=0, nextj=0+0=0&lt;br\/>Check: (0,0) valid but vis[0][0]=1 \u274c&lt;br\/>Already visited\"]\n    \n    %% Level 2: From (2,0), loop through 4 directions\n    A1 --- A1a[\"ind=0: D (Down)&lt;br\/>nexti=2+1=3, nextj=0+0=0&lt;br\/>Check: (3,0) valid but mat[3][0]=0 \u274c&lt;br\/>Blocked cell\"]\n    A1 --- A1b[\"ind=1: L (Left)&lt;br\/>nexti=2+0=2, nextj=0-1=-1&lt;br\/>Check: nextj=-1 &lt; 0 \u274c&lt;br\/>Out of bounds\"]\n    A1 --- A1c[\"ind=2: R (Right)&lt;br\/>nexti=2+0=2, nextj=0+1=1&lt;br\/>Check: (2,1) valid, mat[2][1]=1 \u2713&lt;br\/>Mark vis[2][0]=1, move='DDR'&lt;br\/>Recurse to (2,1)\"]\n    A1 --- A1d[\"ind=3: U (Up)&lt;br\/>nexti=2-1=1, nextj=0+0=0&lt;br\/>Check: (1,0) valid but vis[1][0]=1 \u274c&lt;br\/>Already visited\"]\n    \n    %% Level 2: From (1,1), loop through 4 directions\n    A3 --- A3a[\"ind=0: D (Down)&lt;br\/>nexti=1+1=2, nextj=1+0=1&lt;br\/>Check: (2,1) valid, mat[2][1]=1 \u2713&lt;br\/>Mark vis[1][1]=1, move='DRD'&lt;br\/>Recurse to (2,1)\"]\n    A3 --- A3b[\"ind=1: L (Left)&lt;br\/>nexti=1+0=1, nextj=1-1=0&lt;br\/>Check: (1,0) valid but vis[1][0]=1 \u274c&lt;br\/>Already visited\"]\n    A3 --- A3c[\"ind=2: R (Right)&lt;br\/>nexti=1+0=1, nextj=1+1=2&lt;br\/>Check: (1,2) valid but mat[1][2]=0 \u274c&lt;br\/>Blocked cell\"]\n    A3 --- A3d[\"ind=3: U (Up)&lt;br\/>nexti=1-1=0, nextj=1+0=1&lt;br\/>Check: (0,1) valid but mat[0][1]=0 \u274c&lt;br\/>Blocked cell\"]\n    \n    %% Level 3: From (2,1) via path DDR\n    A1c --- A1c1[\"ind=0: D (Down)&lt;br\/>nexti=2+1=3, nextj=1+0=1&lt;br\/>Check: (3,1) valid, mat[3][1]=1 \u2713&lt;br\/>Mark vis[2][1]=1, move='DDRD'&lt;br\/>Recurse to (3,1)\"]\n    A1c --- A1c2[\"ind=1: L (Left)&lt;br\/>nexti=2+0=2, nextj=1-1=0&lt;br\/>Check: (2,0) valid but vis[2][0]=1 \u274c&lt;br\/>Already visited\"]\n    A1c --- A1c3[\"ind=2: R (Right)&lt;br\/>nexti=2+0=2, nextj=1+1=2&lt;br\/>Check: (2,2) valid but mat[2][2]=0 \u274c&lt;br\/>Blocked cell\"]\n    A1c --- A1c4[\"ind=3: U (Up)&lt;br\/>nexti=2-1=1, nextj=1+0=1&lt;br\/>Check: (1,1) valid, mat[1][1]=1 \u2713&lt;br\/>Mark vis[2][1]=1, move='DDRU'&lt;br\/>Recurse to (1,1)\"]\n    \n    %% Level 3: From (2,1) via path DRD\n    A3a --- A3a1[\"ind=0: D (Down)&lt;br\/>nexti=2+1=3, nextj=1+0=1&lt;br\/>Check: (3,1) valid, mat[3][1]=1 \u2713&lt;br\/>Mark vis[2][1]=1, move='DRDD'&lt;br\/>Recurse to (3,1)\"]\n    A3a --- A3a2[\"ind=1: L (Left)&lt;br\/>nexti=2+0=2, nextj=1-1=0&lt;br\/>Check: (2,0) valid, mat[2][0]=1 \u2713&lt;br\/>Mark vis[2][1]=1, move='DRDL'&lt;br\/>Recurse to (2,0)\"]\n    A3a --- A3a3[\"ind=2: R (Right)&lt;br\/>nexti=2+0=2, nextj=1+1=2&lt;br\/>Check: (2,2) valid but mat[2][2]=0 \u274c&lt;br\/>Blocked cell\"]\n    A3a --- A3a4[\"ind=3: U (Up)&lt;br\/>nexti=2-1=1, nextj=1+0=1&lt;br\/>Check: (1,1) valid but vis[1][1]=1 \u274c&lt;br\/>Already visited\"]\n    \n    %% Level 4: From (3,1) via path DDRD, continue to find (3,3)\n    A1c1 --- A1c1c[\"ind=2: R (Right)&lt;br\/>nexti=3+0=3, nextj=1+1=2&lt;br\/>Check: (3,2) valid, mat[3][2]=1 \u2713&lt;br\/>Mark vis[3][1]=1, move='DDRDR'&lt;br\/>Recurse to (3,2)\"]\n    \n    %% Level 4: From (3,1) via path DRDD, continue to find (3,3)\n    A3a1 --- A3a1c[\"ind=2: R (Right)&lt;br\/>nexti=3+0=3, nextj=1+1=2&lt;br\/>Check: (3,2) valid, mat[3][2]=1 \u2713&lt;br\/>Mark vis[3][1]=1, move='DRDDR'&lt;br\/>Recurse to (3,2)\"]\n    \n    %% Level 5: From (3,2), reach destination (3,3)\n    A1c1c --- A1c1c3[\"ind=2: R (Right)&lt;br\/>nexti=3+0=3, nextj=2+1=3&lt;br\/>Check: (3,3) valid, mat[3][3]=1 \u2713&lt;br\/>i=3, j=3 == n-1=3 \u2713&lt;br\/>Found destination!&lt;br\/>move='DDRDDR'\"]\n    \n    A3a1c --- A3a1c3[\"ind=2: R (Right)&lt;br\/>nexti=3+0=3, nextj=2+1=3&lt;br\/>Check: (3,3) valid, mat[3][3]=1 \u2713&lt;br\/>i=3, j=3 == n-1=3 \u2713&lt;br\/>Found destination!&lt;br\/>move='DRDDRR'\"]\n    \n    %% Success cases\n    A1c1c3 --- Success1[\"\u2705 Add 'DDRDDR' to result&lt;br\/>Backtrack and unmark vis arrays\"]\n    A3a1c3 --- Success2[\"\u2705 Add 'DRDDRR' to result&lt;br\/>Backtrack and unmark vis arrays\"]\n    \n    %% Final result\n    Success1 --- Final[\"Final Result: ['DDRDDR', 'DRDDRR']\"]\n    Success2 --- Final\n\n    %% Styling\n    style Success1 fill:#90EE90\n    style Success2 fill:#90EE90\n    style Final fill:#90EE90\n    \n    style B fill:#FFB6C1\n    style C fill:#FFB6C1\n    style D fill:#FFB6C1\n    style A2 fill:#FFB6C1\n    style A4 fill:#FFB6C1\n    style A1a fill:#FFB6C1\n    style A1b fill:#FFB6C1\n    style A1d fill:#FFB6C1\n    style A3b fill:#FFB6C1\n    style A3c fill:#FFB6C1\n    style A3d fill:#FFB6C1\n    \n    style A1c1c fill:#87CEEB\n    style A3a1c fill:#87CEEB\n    style A1c1 fill:#87CEEB\n    style A3a1 fill:#87CEEB\n    \n    style Root fill:#E6E6FA\n<\/pre><\/div>\n\n\n\n<p>For detailed dry run [<strong><a href=\"https:\/\/mermaid.live\/edit#pako:eNrNWE1v4zYQ_StTFYs4WDkVSTuJhVUBJ7JPKQpom0ttH2iJtrWRJUOSs0mDHHvrrdftn9tfUlLfH5aspAHSJDBEDsl58-bNiM6TZHoWk1Rp7dPdBn7T5y7wH8PzwtlcCjznnvUUWZFh690z7eREhns70KjjgHL6aen_9PMvNPTtBxVmMySLhcpC5k_iGWVPYo6Pxe9iEe2ybG32Md7Q5-vA-qLNxKMsJsXY9rUT_ca4PYmWfw6pHwINQWA5lYEP14yPiExO59Iixhx_fvgAN-yecXwqTH1vm25xPG8H4cb39usNDIQDZoa25wbQs11LE_CwOC0LH_r9Pow5CZFZBR16uvfVjaN22UNoa8pHpCEZxOALHyiaEhmvN8y8U6HHQzkF24Wlt3etAL5_-ztib4YWM2WhKfHElobJBBITCaf-XbRSiQ0p-3rMhsHMvR8wCL3YR8ZABvsqgY1UuIHeDVuFZdgcaQa7j7Q-KuKO5_sIPgHH-M9fke3XfQjeKgml7vA6cYhVMKBn2OtNi0fBWokoTv5Bonj4qERUNpGgunI8845ZYDLHqYPSE1BEhVvo3e5KiKKwG3MXL-rEQUV2KJUdapddvG0cqwy1ygxxwnCzzLCQ2T11bCsmCTepCVXUdEBOuCinBBxuFRPieNCbiClxR9qlVPZXkxISUiqQgSLFdCDDOFRbqEbGoEVTiEevNOdJyfIES05Aob4zYsaOz6j1KGx2yKwmjeFUY7iTxlAiMtqqMsy5JM3oSRm94JakfaytGjPvy1YZYe4Qv42MUodmu5DKHmtCwhUh4SYh4WpVGYfKqqikFKDVoiXcP_5qKWsJ_UctCbUf1xJJipR271hRxb6O26R68yLVj3Gb4lt2b1pR2b4VuxkA8wVtLKKrggBXq40jwMerLXVvde1T9ewoWXYy353euxVhkbxJifNsCjsaboDXR1oGZlqoqHtjqsMlFTGRlkJF5UI9oCZSrtQMIu7evep6wnU94a56yiGQF_SzuqJwXVG4k6JyAIOu_aqepM6v5XqSbo-8mDvKztDTCqFpC3sf2Rn6UdnlEN9IdkcuhnWIN8euhjnEd5JlDuBNZFls9OgVr9FBKjtS7Xa6DKbnhra7j3hccajJF9e0vrILy7ErC-EBkGYuScZlJkl8MN-k3gmNQ5rEpy8Nl4v7SLi87LL6e6dwDf2l4Q7zcDG_JHFFmBuwWMDDpOJ2VE1o_mY71rVLMUYtpxIjqcZIijHaYvMXjYCmgcu1TjLLVNyKixh_iKbzjHMOKuFGKcmT8_9ELoDXkPNEfd6bJgsCMGnAgkIm4gtRYhUd__u3P2FsWZCSIJLvs2DvhHG3oeZd6PMPoBzF3t0mKgLq-_QxKDagyuG4dHiM85WHZ1FNOQVOckI8mUYSeY7M3G28zIiWqTBLQ5MzHIvs6BRsvn_u5iSGj47truNxwAcs97eyHUf9caRMJiPlwALcuCAGV7cW11wl9un06vwaFS3XjRa90TLGzaZBswnRFtuyxWY120jLPmK22A6dWfYq2ky85vLiejK5Ku-nbVbxzmnbesBYXBL9hy1eMjmfnE_Hc1eSpbVvW5Ia-nsmS1vmb6kYSk9i41wKN2zL5pLKHy22okLO0tx95tt21P3d87bpzuibp6SuqBPw0X5n0ZDpNl37dJvN-sy1mH_N-0QoqUQhw-gUSX2SHiR1qJAzjEdowP8uh_xDlh4ldUTOFGV0ORgOL4ZDMjhHz7L0R-RWObu4xIMhHhEFX6ARev4XBQ_aLQ\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Click here<\/span><\/mark><\/a><\/strong>]<\/p>\n\n\n\n<p><strong>Same exploration pattern as brute force, but with cleaner code structure<\/strong><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"14-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>\u00a0O(4^(N\u00d7N)) &#8211; Same as brute force, no algorithmic improvement<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>\u00a0O(N\u00d7N) &#8211; Same space requirements as brute force<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"15-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This approach is like giving the rat a smart compass that automatically points to all four directions, so instead of manually checking &#8220;down, left, right, up&#8221;, the rat just follows the compass directions in order. The exploration is identical, but the implementation is much more elegant and maintainable.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"16-summary\">Summary<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Approach<\/th><th>Time<\/th><th>Space<\/th><th>Difficulty<\/th><th>Best For<\/th><\/tr><\/thead><tbody><tr><td>Brute Force (Explicit Directions)<\/td><td>O(4^(N\u00d7N))<\/td><td>O(N\u00d7N)<\/td><td>Medium<\/td><td>Understanding the concept<\/td><\/tr><tr><td>Optimal (Direction Arrays)<\/td><td>O(4^(N\u00d7N))<\/td><td>O(N\u00d7N)<\/td><td>Medium<\/td><td>Production code<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>The&nbsp;<strong>optimal approach<\/strong>&nbsp;doesn&#8217;t improve time complexity but provides significant benefits:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Code Maintainability<\/strong>\u00a0&#8211; Single loop instead of 4 separate if-statements<\/li>\n\n\n\n<li><strong>Reduced Bugs<\/strong>\u00a0&#8211; Less code duplication means fewer places for errors<\/li>\n\n\n\n<li><strong>Scalability<\/strong>\u00a0&#8211; Easy to extend to 8-direction movement (add more directions to arrays)<\/li>\n\n\n\n<li><strong>Readability<\/strong>\u00a0&#8211; Cleaner, more professional code structure<\/li>\n<\/ol>\n\n\n\n<p>The key insight for Rat in a Maze is recognizing that backtracking problems often involve repetitive patterns that can be elegantly handled with arrays and loops. The direction array technique is widely used in grid-based problems like word search, number of islands, and shortest path algorithms!<\/p>\n\n\n\n<p>Both solutions use the same core algorithm &#8211;&nbsp;<strong>backtracking with DFS<\/strong>&nbsp;&#8211; but the optimal solution demonstrates how thoughtful code organization can make algorithms more maintainable without sacrificing performance.<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Consider a rat placed at position (0, 0) in an&nbsp;n x n&nbsp;square matrix&nbsp;mat[][]. The rat&#8217;s goal is to reach the destination at position (n-1, n-1). The rat can move in four possible directions:&nbsp;&#8216;U'(up),&nbsp;&#8216;D'(down),&nbsp;&#8216;L&#8217; (left),&nbsp;&#8216;R&#8217; (right). The matrix contains only two possible values: Your task is to find&nbsp;all possible paths&nbsp;the rat can take to reach the<\/p>\n","protected":false},"author":1,"featured_media":773,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[32,19],"class_list":{"0":"post-772","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-intermediate","9":"tag-advance-recursion","10":"tag-medium"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/07\/rat-in-a-maze-problem-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/772","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=772"}],"version-history":[{"count":1,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/772\/revisions"}],"predecessor-version":[{"id":774,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/772\/revisions\/774"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/773"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=772"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=772"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=772"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}