6boris · 6boris · May 27, 2025 · May 18, 2025
diff --git a/leetcode/1901-2000/1931.Painting-a-Grid-With-Three-Different-Colors/1.png b/leetcode/1901-2000/1931.Painting-a-Grid-With-Three-Different-Colors/1.png
diff --git a/leetcode/1901-2000/1931.Painting-a-Grid-With-Three-Different-Colors/2.png b/leetcode/1901-2000/1931.Painting-a-Grid-With-Three-Different-Colors/2.png
diff --git a/leetcode/1901-2000/1931.Painting-a-Grid-With-Three-Different-Colors/README.md b/leetcode/1901-2000/1931.Painting-a-Grid-With-Three-Different-Colors/README.md
@@ -1,28 +1,36 @@
 # [1931.Painting a Grid With Three Different Colors][title]
 
-> [!WARNING|style:flat]
-> This question is temporarily unanswered if you have good ideas. Welcome to [Create Pull Request PR](https://github.com/kylesliu/awesome-golang-algorithm)
-
 ## Description
+You are given two integers `m` and `n`. Consider an m x n grid where each cell is initially white. You can paint each cell **red**, **green**, or **blue**. All cells **must** be painted.
+
+Return the number of ways to color the grid with **no two adjacent cells having the same color**. Since the answer can be very large, return it **modulo** `10^9 + 7`.
 
-**Example 1:**
+**Example 1:**  
+
+![1](./1.png)
 
 ```
-Input: a = "11", b = "1"
-Output: "100"
+Input: m = 1, n = 1
+Output: 3
+Explanation: The three possible colorings are shown in the image above.
 ```
 
-## 题意
-> ...
+**Example 2:**  
 
-## 题解
+![2](./2.png)
 
-### 思路1
-> ...
-Painting a Grid With Three Different Colors
-```go
+```
+Input: m = 1, n = 2
+Output: 6
+Explanation: The six possible colorings are shown in the image above.
 ```
 
+**Example 3:**
+
+```
+Input: m = 5, n = 5
+Output: 580986
+```
 
 ## 结语
 

diff --git a/leetcode/1901-2000/1931.Painting-a-Grid-With-Three-Different-Colors/Solution.go b/leetcode/1901-2000/1931.Painting-a-Grid-With-Three-Different-Colors/Solution.go
@@ -1,5 +1,65 @@
 package Solution
 
-func Solution(x bool) bool {
-	return x
+const mod1931 = 1e9 + 7
+
+var colors = []byte{'R', 'G', 'B'}
+
+func columns(m int, cur string, preColor byte) []string {
+	ans := []string{}
+	if m == 0 {
+		ans = append(ans, cur)
+		return ans
+	}
+
+	for _, color := range colors {
+		if color != preColor {
+			ans = append(ans, columns(m-1, cur+string(color), color)...)
+		}
+	}
+	return ans
+}
+func can(a, b string) bool {
+	for i := 0; i < len(a); i++ {
+		if a[i] == b[i] {
+			return false
+		}
+	}
+	return true
+}
+
+func Solution(m int, n int) int {
+	groups := columns(m, "", ' ')
+	cache := make(map[string]map[int]int)
+	var dfs func(int, string) int
+	dfs = func(left int, cur string) int {
+		if left == 0 {
+			return 1
+		}
+		if v, ok := cache[cur]; ok {
+			if c, ok1 := v[left]; ok1 {
+				return c
+			}
+		}
+		ans := 0
+		for i := 0; i < len(groups); i++ {
+			if !can(cur, groups[i]) {
+				continue
+			}
+			ans = (ans + dfs(left-1, groups[i])) % mod1931
+		}
+
+		v, ok := cache[cur]
+		if !ok {
+			v = map[int]int{}
+		}
+		v[left] = ans
+		cache[cur] = v
+		return ans
+	}
+	// 挑选n个
+	cur := ""
+	for i := 0; i < m; i++ {
+		cur += " "
+	}
+	return dfs(n, cur)
 }
diff --git a/leetcode/1901-2000/1931.Painting-a-Grid-With-Three-Different-Colors/Solution_test.go b/leetcode/1901-2000/1931.Painting-a-Grid-With-Three-Different-Colors/Solution_test.go
@@ -10,30 +10,30 @@ func TestSolution(t *testing.T) {
 	//	测试用例
 	cases := []struct {
 		name   string
-		inputs bool
-		expect bool
+		m, n   int
+		expect int
 	}{
-		{"TestCase", true, true},
-		{"TestCase", true, true},
-		{"TestCase", false, false},
+		{"TestCase1", 1, 1, 3},
+		{"TestCase2", 1, 2, 6},
+		{"TestCase3", 5, 5, 580986},
 	}
 
 	//	开始测试
 	for i, c := range cases {
 		t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
-			got := Solution(c.inputs)
+			got := Solution(c.m, c.n)
 			if !reflect.DeepEqual(got, c.expect) {
-				t.Fatalf("expected: %v, but got: %v, with inputs: %v",
-					c.expect, got, c.inputs)
+				t.Fatalf("expected: %v, but got: %v, with inputs: %v %v",
+					c.expect, got, c.m, c.n)
 			}
 		})
 	}
 }
 
-//	压力测试
+// 压力测试
 func BenchmarkSolution(b *testing.B) {
 }
 
-//	使用案列
+// 使用案列
 func ExampleSolution() {
 }