JAVA||O(3*2^(m-1)*n)||EASY UNDERSTANDING||
\nclass Solution \n{\n    static int mod=(int)(1e9+7);\n   public static int dfs(int n,ArrayList<ArrayList<Integer>> arr,int src,int dp[][])\n   {\n       if(n=
```\nclass Solution \n{\n    static int mod=(int)(1e9+7);\n   public static int dfs(int n,ArrayList<ArrayList<Integer>> arr,int src,int dp[][])\n   {\n       if(n==0)\n       {\n           return 1;\n       }\n       if(dp[n][src]!=-1)\n       {\n           return dp[n][src];\n       }\n       int val=0;\n    for(Integer ap:arr.get(src))\n    {\n         val=(val%mod+dfs(n-1,arr,ap,dp)%mod)%mod;\n    }\n       return dp[n][src]=val;\n   }\n   public static void val(ArrayList<String> arr,int color,int m,String s)\n    {\n        if(m==0)\n        {\n            arr.add(s);\n            return;\n        }\n       for(int i=0;i<3;i++)\n       {\n           if(color!=i)\n           val(arr,i,m-1,s+i);\n       }\n    }\n    public static boolean Match(String s,String s1)\n    {\n        for(int i=0;i<s.length();i++)\n        {\n            if(s.charAt(i)==s1.charAt(i))\n            {\n                return false;\n            }\n        }\n        return true;\n    }\n    public int colorTheGrid(int m, int n)\n    {\n        ArrayList<String> arr=new ArrayList<String>();\n        for(int i=0;i<3;i++)\n        {\n            String s="";\n            val(arr,i,m-1,s+i);\n        }\n        ArrayList<ArrayList<Integer>> adj=new ArrayList<ArrayList<Integer>>();\n        for(int i=0;i<arr.size();i++)\n        {\n            adj.add(new ArrayList<Integer>());\n        }\n    \n        for(int i=0;i<adj.size();i++)\n        {\n            for(int j=0;j<arr.size();j++)\n            {\n                if(Match(arr.get(i),arr.get(j)))\n                {\n                    adj.get(i).add(j);\n                }\n            }\n        }\n  int dp[][]=new int[n+1][adj.size()+1];\n        for(int i=0;i<=n;i++)\n        {\n            Arrays.fill(dp[i],-1);\n        }\n        int sum12=0;\n        for(int i=0;i<arr.size();i++)\n        {\n                 sum12=(sum12%mod+dfs(n-1,adj,i,dp)%mod)%mod;\n        }\n        return sum12;\n       \n    }\n}\n```\nsuppose u have to find the adjacent column u can simply find the column combination using bitmasking \nfor example\n```\n   public static void val(ArrayList<String> arr,int color,int m,String s)\n    {\n        if(m==0)\n        {\n            arr.add(s);\n            return;\n        }\n       for(int i=0;i<3;i++)\n       {\n           if(color!=i)\n           val(arr,i,m-1,s+i);\n       }\n    }\n```\n\n\n```\nu will get suppose we take m=5 and n=5\n[01010, 01012, 01020, 01021, 01201, 01202, 01210, 01212, 02010, 02012, 02020, 02021, 02101, 02102, 02120, 02121, 10101, 10102, 10120, 10121, 10201, 10202, 10210, 10212, 12010, 12012, 12020, 12021, 12101, 12102, 12120, 12121, 20101, 20102, 20120, 20121, 20201, 20202, 20210, 20212, 21010, 21012, 21020, 21021, 21201, 21202, 21210, 21212]\nwhere 0=Red 1=Green 2=Blue\nthen u can simply find which elements connect which element will connect to which element means which element is appropriate for next column\n0->[16, 17, 19, 20, 21, 28, 29, 31, 32, 33, 35, 36, 37]\n1->[16, 18, 19, 20, 28, 30, 31, 32, 34, 35, 36]\n2->[16, 17, 20, 21, 23, 28, 29, 32, 33, 36, 37, 39]\n3->[17, 21, 22, 23, 29, 33, 37, 38, 39]\n4->[18, 24, 25, 26, 30, 34]\n5->[18, 19, 24, 26, 27, 30, 31, 34, 35]\n6->[16, 17, 19, 27, 28, 29, 31, 32, 33, 35]\n7->[16, 18, 19, 26, 27, 28, 30, 31, 32, 34, 35]\n8->[16, 17, 19, 20, 21, 32, 33, 35, 36, 37, 44, 45]\n9->[16, 18, 19, 20, 32, 34, 35, 36, 44]\n10->[16, 17, 20, 21, 23, 32, 33, 36, 37, 39, 44, 45, 47]\n11->[17, 21, 22, 23, 33, 37, 38, 39, 45, 46, 47]\n12->[22, 23, 38, 39, 40, 41, 42, 46, 47]\n13->[22, 38, 40, 42, 43, 46]\n14->[20, 21, 23, 36, 37, 39, 41, 44, 45, 47]\n15->[21, 22, 23, 37, 38, 39, 40, 41, 45, 46, 47]\n16->[0, 1, 2, 6, 7, 8, 9, 10, 40, 41, 42, 46, 47]\n17->[0, 2, 3, 6, 8, 10, 11, 40, 42, 43, 46]\n18->[1, 4, 5, 7, 9, 41, 44, 45, 47]\n19->[0, 1, 5, 6, 7, 8, 9, 40, 41, 45, 46, 47]\n20->[0, 1, 2, 8, 9, 10, 14, 40, 41, 42]\n21->[0, 2, 3, 8, 10, 11, 14, 15, 40, 42, 43]\n22->[3, 11, 12, 13, 15, 43]\n23->[2, 3, 10, 11, 12, 14, 15, 42, 43]\n24->[4, 5, 32, 33, 35, 36, 37, 44, 45]\n25->[4, 32, 34, 35, 36, 44]\n26->[4, 5, 7, 32, 33, 36, 37, 39, 44, 45, 47]\n27->[5, 6, 7, 33, 37, 38, 39, 45, 46, 47]\n28->[0, 1, 2, 6, 7, 38, 39, 40, 41, 42, 46, 47]\n29->[0, 2, 3, 6, 38, 40, 42, 43, 46]\n30->[1, 4, 5, 7, 36, 37, 39, 41, 44, 45, 47]\n31->[0, 1, 5, 6, 7, 37, 38, 39, 40, 41, 45, 46, 47]\n32->[0, 1, 2, 6, 7, 8, 9, 10, 24, 25, 26]\n33->[0, 2, 3, 6, 8, 10, 11, 24, 26, 27]\n34->[1, 4, 5, 7, 9, 25]\n35->[0, 1, 5, 6, 7, 8, 9, 24, 25]\n36->[0, 1, 2, 8, 9, 10, 14, 24, 25, 26, 30]\n37->[0, 2, 3, 8, 10, 11, 14, 15, 24, 26, 27, 30, 31]\n38->[3, 11, 12, 13, 15, 27, 28, 29, 31]\n39->[2, 3, 10, 11, 12, 14, 15, 26, 27, 28, 30, 31]\n40->[12, 13, 15, 16, 17, 19, 20, 21, 28, 29, 31]\n41->[12, 14, 15, 16, 18, 19, 20, 28, 30, 31]\n42->[12, 13, 16, 17, 20, 21, 23, 28, 29]\n43->[13, 17, 21, 22, 23, 29]\n44->[8, 9, 10, 14, 18, 24, 25, 26, 30]\n45->[8, 10, 11, 14, 15, 18, 19, 24, 26, 27, 30, 31]\n46->[11, 12, 13, 15, 16, 17, 19, 27, 28, 29, 31]\n47->[10, 11, 12, 14, 15, 16, 18, 19, 26, 27, 28, 30, 31]\nif in first column we put-------> second column we put\n01010(0 index in adj)------>10101(16th index) and so on.....\n```\n\nthen do dfs\n  ```\nstatic int mod=(int)(1e9+7);\n   public static int dfs(int n,ArrayList<ArrayList<Integer>> arr,int src,int dp[][])\n   {\n       if(n==0)\n       {\n           return 1;\n       }\n       if(dp[n][src]!=-1)\n       {\n           return dp[n][src];\n       }\n       int val=0;\n    for(Integer ap:arr.get(src))\n    {\n         val=(val%mod+dfs(n-1,arr,ap,dp)%mod)%mod;\n    }\n       return dp[n][src]=val;\n   }\n  static int mod=(int)(1e9+7);\n   public static int dfs(int n,ArrayList<ArrayList<Integer>> arr,int src,int dp[][])\n   {\n       if(n==0)\n       {\n           return 1;\n       }\n       if(dp[n][src]!=-1)\n       {\n           return dp[n][src];\n       }\n       int val=0;\n    for(Integer ap:arr.get(src))\n    {\n         val=(val%mod+dfs(n-1,arr,ap,dp)%mod)%mod;\n    }\n       return dp[n][src]=val;\n   }\n```\n\n\n\ni think it is pretty clear so\n** PLS UPVOTE TO MOTIVATE ME**
['Dynamic Programming', 'Depth-First Search', 'Java']