算法分析
-
dfs(x,y,cnt)
表示当前已走到(x,y)
坐标,且该坐标已被表示过,cnt
表示已走的点的数量 -
向
8
个方向深度优先遍历每一个情况,若cnt == n * m
,表示当前遍历方式已走过所有点,更新res
参考文献
算法提高课
Java 代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N = 10;
static int n;
static int m;
static boolean[][] st = new boolean[N][N];//标识该坐标是否走过
static int[] dx = new int[] {-2,-1,1,2,2,1,-1,-2};
static int[] dy = new int[] {1,2,2,1,-1,-2,-2,-1};
static int res = 0;
static void dfs(int x,int y,int cnt)
{
if(cnt == n * m)
{
res ++;
return;
}
for(int i = 0;i < 8;i ++)
{
int a = x + dx[i];
int b = y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;
if(st[a][b]) continue;
st[a][b] = true;
cnt ++;
dfs(a,b,cnt);
cnt --; //恢复现场
st[a][b] = false; //恢复现场
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int T = scan.nextInt();
while(T -- > 0)
{
n = scan.nextInt();
m = scan.nextInt();
int x = scan.nextInt();
int y = scan.nextInt();
res = 0;
st[x][y] = true;
dfs(x,y,1);
st[x][y] = false; //恢复现场
System.out.println(res);
}
}
}