golang 解法, 执行用时: 12 ms, 内存消耗: 1.8 MB, 提交时间: 2023-10-22 10:19:12

func cal(m,n int, u,i0,j0 uint)int {
     if 0==n {
        return 1
    }
    o:=0
    if m<=0 {
        o++
    }
    var i,j uint
    for  i = 0; i < 3; i++ {
        for j = 0; j < 3; j++ {
            i1,j1,u1 := i0 + i,  j0 + j,  u | (1 << (i * 3 + j));
                if u1 > u && (i1&1==1 || j1&1==1 || u1 & (1 << (i1 / 2 * 3 + j1 / 2))!=0) {
                    o += cal(m - 1, n - 1, u1, i, j);
                }
            }
        }
        return o
    }

func numberOfPatterns(m int, n int) int {
    return cal(m, n, 0, 1, 1)
}

golang 解法, 执行用时: 60 ms, 内存消耗: 1.8 MB, 提交时间: 2023-10-22 10:18:59

func numberOfPatterns(m int, n int) int {
	uf := NewUnionFindSet(10)
	used := make([]bool, 10)
	ans := 0

	uf.Mix(1, 3)
	uf.Mix(1, 9)
	uf.Mix(1, 7)
	uf.Mix(4, 6)
	uf.Mix(2, 8)

	var dfs func(currentPoint int, curCnt int)
	dfs = func(currentPoint int, curCnt int) {
		if curCnt >= m && curCnt <= n {
			ans++
		} else if curCnt > n {
			return
		}

		used[currentPoint ] = true
		for i := 1; i <= 9; i++ {
			needCross := uf.connected(i, currentPoint )

			if !used[i] && (!needCross || used[(currentPoint  + i) / 2]) {
				dfs(i, curCnt + 1)
			}
		}
		used[currentPoint ] = false
	}

	for i := 1; i < 10; i++ {
		dfs(i, 1)
	}
	return ans
}

// UnionFindSet 并查集结构体
type UnionFindSet struct {
	id    []int // 分量id
	sz    []int //由触点索引的各个根节点对应的分量大小
	count int   // 连通分量数量
}

//初始化分量id数组
func NewUnionFindSet(n int) *UnionFindSet {
	id := make([]int, n)
	for i := range id {
		id[i] = i
	}

	sz := make([]int, n)
	for i := range sz {
		sz[i] = i
	}

	return &UnionFindSet{
		id:    id,
		sz :   sz,
		count: n,
	}
}

func (u *UnionFindSet) Find(p int) int {
	for p != u.id[p] {
		p = u.id[p]
	}
	return p
}

func (u *UnionFindSet) Mix(p, q int) {
	i := u.Find(p)
	j := u.Find(q)
	if i == j {
		return
	}
	if u.sz[i] < u.sz[j] {
		u.id[i] = j
		u.sz[j] += u.sz[i]
	} else {
		u.id[j] = i
		u.sz[i] += u.sz[j]
	}
	u.count--
}

func (u *UnionFindSet) connected(p, q int) bool {
	return u.Find(p) == u.Find(q)
}

cpp 解法, 执行用时: 32 ms, 内存消耗: 6.4 MB, 提交时间: 2023-10-22 10:18:40

class Solution {
public:
    vector<int> dp;
    vector<int> check = vector<int>(9, 0);
    int ans = 0;

    void dfs(int step, int m, int n, int x, int y) {
        if (step >= m && step <= n) {
            ans++;
        }
        if (step == n) {
            return;
        }

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (x == i && y == j) continue;
                if (check[i*3+j]) continue;
                if (abs(x-i) % 2 == 0 && abs(y-j) % 2 == 0 && !check[(x+i)/2*3+(y+j)/2]) continue;
                check[i*3+j] = 1;
                dfs(step+1, m, n, i, j);
                check[i*3+j] = 0;
            }
        }
    }

    int numberOfPatterns(int m, int n) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                check[i*3+j] = 1;
                dfs(1, m, n, i, j);
                check[i*3+j] = 0;
            }
        }
        return ans;
    }
};

java 解法, 执行用时: 8 ms, 内存消耗: 39.9 MB, 提交时间: 2023-10-22 10:18:13

class Solution {
    public int numberOfPatterns(int m, int n) {
        
        int[][][] dp = new int[n][9][1<<9];
        
        for(int j=0; j<9; j++) dp[0][j][1<<j] = 1;
        
        for(int i=1; i<n; i++){
            for(int j=0; j<9; j++){
                for(int k=0; k<9; k++){
                    for(int x=0; x<(1<<9); x++){
                        if(dp[i-1][k][x]==0 || (x & (1<<j) )!=0 ) continue;
                        if(connect(x, k, j)) dp[i][j][x | (1<<j)] += dp[i-1][k][x];
                    }
                }
            }
        }
        
        int ans = 0;
        for(int i=m-1; i<n; i++){
            for(int j=0; j<9; j++){
                for(int x=0; x<(1<<9); x++) ans += dp[i][j][x];
            }
        }
        
        return ans;
    }
    
    int[][] dict = new int[9][9];
    {
        // 横
        dict[0][2] = dict[2][0] = (1<<1);
        dict[3][5] = dict[5][3] = (1<<4);
        dict[6][8] = dict[8][6] = (1<<7);
        // 竖
        dict[0][6] = dict[6][0] = (1<<3);
        dict[1][7] = dict[7][1] = (1<<4);
        dict[2][8] = dict[8][2] = (1<<5);
        // 对角
        dict[0][8] = dict[8][0] = (1<<4);
        dict[2][6] = dict[6][2] = (1<<4);
    }
    
    boolean connect(int x, int k, int j){
        return k!=j && (dict[k][j]==0 || (x&dict[k][j])!=0);
    }
    
}

python3 解法, 执行用时: 52 ms, 内存消耗: 17.2 MB, 提交时间: 2023-10-22 10:17:20

from functools import lru_cache


class Solution:
    def numberOfPatterns(self, m: int, n: int) -> int:
        graph = {
            1: {3: 2, 7: 4, 9: 5},
            2: {8: 5},
            3: {1: 2, 7: 5, 9: 6},
            4: {6: 5},
            5: {},
            6: {4: 5},
            7: {1: 4, 3: 5, 9: 8},
            8: {2: 5},
            9: {1: 5, 3: 6, 7: 8},
        }
        ans = 0

        @lru_cache(None)
        def dfs(status, current, count):
            if count == n:
                return 1
            current_ans = 0 if count < m else 1
            for i in range(1, 10):
                if status & (1 << i) == 0:
                    if i not in graph[current] or ((1 << graph[current][i]) & status):
                        current_ans += dfs(status | (1 << i), i, count + 1)
            return current_ans

        # for cur in range(1, 10):
            # ans += dfs(1 << cur, cur, 1)
        
        ans += 4 * dfs(1 << 1, 1, 1)
        ans += 4 * dfs(1 << 2, 2, 1)
        ans += dfs(1 << 5, 5, 1)

        return ans

java 解法, 执行用时: 39 ms, 内存消耗: 38.2 MB, 提交时间: 2023-10-22 10:17:03

public class Solution {

    private boolean used[] = new boolean[9];

    public int numberOfPatterns(int m, int n) {	        
        int res = 0;
        for (int len = m; len <= n; len++) {	            
            res += calcPatterns(-1, len);
            for (int i = 0; i < 9; i++) {	                
                used[i] = false;
            }            
        }
        return res;
    }

    private boolean isValid(int index, int last) {
        if (used[index])
            return false;
        // first digit of the pattern    
        if (last == -1)
            return true;
        // knight moves or adjacent cells (in a row or in a column)	       
        if ((index + last) % 2 == 1)
            return true;
        // indexes are at both end of the diagonals for example 0,0, and 8,8          
        int mid = (index + last)/2;
        if (mid == 4)
            return used[mid];
        // adjacent cells on diagonal  - for example 0,0 and 1,0 or 2,0 and //1,1
        if ((index%3 != last%3) && (index/3 != last/3)) {
            return true;
        }
        // all other cells which are not adjacent
        return used[mid];
    }

    private int calcPatterns(int last, int len) {
        if (len == 0)
            return 1;    
        int sum = 0;
        for (int i = 0; i < 9; i++) {
            if (isValid(i, last)) {
                used[i] = true;
                sum += calcPatterns(i, len - 1);
                used[i] = false;                    
            }
        }
        return sum;
    }
}