【回溯】B039_LQ_方格填数（暴力判断 / dfs）

一、Problem

1580

二、Solution

方法一：暴搜

暴力判断也行。

...

---

方法二：dfs

…???? ????

import java.util.*;
import java.math.*;
import java.io.*;
public class Main{
	static int[][] mp;
	static boolean[] vis;
	static boolean[][] can;
	static int cnt;
	final static int R = 3, C = 4;
	static int[][] dir = {{0,1},{1,0},{0,-1},{-1,0},{1,1},{-1,-1},{-1,1},{1,-1}};
	
	static void check() {
		boolean flag = true;
		for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++) {
			if (!can[i][j])
				continue;
			for (int k = 0; k < 8; k++) {
				int tx = i + dir[k][0];
				int ty = j + dir[k][1];
				if (tx >= 0 && tx < R && ty >=0 && ty < C && can[tx][ty]) {
					if (Math.abs(mp[i][j] - mp[tx][ty]) == 1)
						flag = false;
				}
			}
		}
		if (flag) cnt++;
	}
	static void dfs(int x, int y) {
	    if (x == R-1 && y == C-1) {
			check();
    		return;
		}
		if (y >= C)
		    dfs(x+1, 0);
	    else {
    		for (int i = 0; i < 10; i++) {
    			if (vis[i])
    				continue;
    			vis[i] = true;
    			mp[x][y] = i;
    			dfs(x, y+1);
    			vis[i] = false;
    		}
   		}
	}
    public static void main(String[] args) throws IOException {  
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
		mp = new int[R][C];
		can = new boolean[R][C];
		vis = new boolean[10];
		for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++) {
			can[i][j] = true;
		}
		can[0][0] = false;
		can[2][3] = false;
		dfs(0, 1);
		System.out.println(cnt);
    }
}

复杂度分析

• 时间复杂度：$O(...)$O(...)，
• 空间复杂度：$O(...)$O(...)，