Can't understand how numberOfPatterns(1,2) should return 65 (Solved via DFS, answer inside)


  • 22
    A

    My solutions returns 49: basically it's 9 cases of 1 number and 40 of 2 paths between close neighbors

    Which cases am I missing?


  • 3
    L

    You probably miss pattern of [1->8] and [1->6]


  • 1
    A

    How is it possible?

    My understanding is that by the rules it shouldn't be reachable, because 2,5,4 arent' selected in that path. As I understand, 1-8 or 1-6 shouldn't work similar to case from rules example:
    4 - 1 - 3 - 6, where there is no path between 1-3 which is previously selected

    Is 1-9 also valid in your example?


  • 4
    L

    If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern. No jumps through non selected key is allowed.

    1-8 doesn't jump over any unselected key but 1-9 does (1 -> '4' -> 9)


  • 2
    A

    Thanks! Now it's working, although I think that task description isn't clear


  • 1
    A

    Here is my solution

    public class Solution {
    
        int result = 0;
        int m, n;
    
        boolean[][] marked = new boolean[3][3];
    
        public int numberOfPatterns(int m, int n) {
            this.m = m;
            this.n = n;
    
            for (int r = 0; r <= 2; r++) {
                for (int c = 0; c <= 2; c++) {
                    numberOfPatterns(r, c, 1);
                }
            }
    
            return result;
        }
    
        void numberOfPatterns(int r, int c, int pathLength) {
            if (r < 0 || r >= 3 || c < 0 || c >= 3 || pathLength > n || marked[r][c])
                return;
    
            if (pathLength >= m) {
                result++;
            }
    
            if (pathLength == n)
                return;
    
            marked[r][c] = true;
    
            for (int rc = -1; rc <= 1; rc++) {
                for (int cc = -1; cc <= 1; cc++) {
                    int nr = r + rc;
                    int nc = c + cc;
                    if (nr < 0 || nr > 2 || nc < 0 || nc > 2)
                        continue;
    
                    if (!marked[nr][nc]) {
                        numberOfPatterns(nr, nc, pathLength + 1);
                    } else {
                        numberOfPatterns(r + 2 * rc, c + 2 * cc, pathLength + 1);
                    }
    
                    if (rc == 0 || cc == 0)
                        continue;
    
                    numberOfPatterns(r + 2 * rc, c + cc, pathLength + 1);
                    numberOfPatterns(r + rc, c + 2 * cc, pathLength + 1);
                }
            }
    
            marked[r][c] = false;
        }
    }

  • 3

    I'd even say the description is wrong. In the current picture, the line from 1 to 8 crosses keys 4 and 5 and thus the pattern 1->8 is invalid. The keys shouldn't be shown as touching squares but as separated dots, or the dividing lines should be removed, so that one thinks the shown digits are the keys.


  • 0
    L

    @andy.galkin2 Similar to yours, but more concise, as duplicated checking for index out of bound is not necessary.

    public class Solution {
      private static int[][] dir = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 } };
    
      public int numberOfPatterns(int m, int n) {
        int[][] mat = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
        int[] count = new int[1];
        for (int i = 0; i < 3; i++) {
          for (int j = 0; j < 3; j++) {
            dfs(mat, i, j, 0, count, m, n);
          }
        }
    
        return count[0];
      }
    
      boolean dfs(int[][] mat, int i, int j, int length, int[] count, int m, int n) {
        if (i < 0 || i >= 3 || j < 0 || j >= 3 // index out of bound
           || mat[i][j] < 0 // visited
           || length >= n) // length reaches limit
          return false;
    
        mat[i][j] = -mat[i][j];
        length++;
        if (length >= m)
          count[0]++;
        for (int[] d : dir) {
          int dx = d[0];
          int dy = d[1];
          if (!dfs(mat, i + dx, j + dy, length, count, m, n)) {
            dfs(mat, i + dx * 2, j + dy * 2, length, count, m, n);
          }
          if (dx != 0 && dy != 0) { // dx==0 || dy =0 already covered by (+dx*2, +dy*2) case
            dfs(mat, i + dx * 2, j + dy, length, count, m, n);
            dfs(mat, i + dx, j + dy * 2, length, count, m, n);
          }
        }
        mat[i][j] = -mat[i][j];
    
        return true;
      }
    }
    

  • 0
    C

    I still don't understand how the movement from 1 to 8 is allowed given that 8 is not adjacent to 1 and that you have no previously used digits (other than 1) which you're allowed to move on a second time on your way to 8. As the first questioner pointed out, it also seems to me that the answer should be 49.

    EDIT: Oh I think I finally got it.
    It's weird but when you move diagonally in such a way that the diagonal doesn't cross a square in the middle of it, as would have been the case if it entered in one edge of the square and then left at the other edge, then the square in question is not counted as a square you moved over. So when you move from 1 to 8, though you cross over 4 and 5, since you don't cross 4 and 5 in the "middle", they don't count as cells you travel over.


  • 0
    M

    @linfongi 1 -> 8 jumps through BOTH 4 and 5!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.