个人博客
5种牛,4x4的牧场,稍微模拟一下可以得出结论:
-
结论1:牧场上不存在超过4群的同一种牛(该结论无用)
-
结论2:每个方格的替换策略是唯一的
此外,除了深度爆搜,没有看出其他解法。
因此可以直接dfs,dfs的方法就是:
dfs(小牛) :
for(...) //遍历行
for(...) //遍历列
if(该处老牛可以被小牛替换)
替换之(破坏现场)
for(每种小牛x)
dfs(小牛x)
恢复现场
这样就能保证遍历所有可能情形。
代码如下:
import java.util.Scanner;
public class Main {
static char[][] g = new char[4][4]; //牧场
static int ans = 0; //总方法数
static Triad[] path = new Triad[16]; //保存替换过程
static boolean[][] status = new boolean[4][4]; //某块牧场是否已被替换
static int[] num = {3,3,3,4,3}; //每种小牛剩余数
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for(int i = 0; i < 4; i++)
g[i] = sc.nextLine().toCharArray();
// for(int i = 0; i < 5; i++)
// dfs((char)(i+'A'), 0); //ABCDE每种小牛都可以作为第一种替换的小牛,起始步数为0,步数为16时说明该种方法成功。
dfs('D',0); //可以直接使用提示
System.out.println(ans);
}
private static void dfs(char c, int step) {
if(step == 16) {
ans++;
if(ans == 1) { //爆搜顺序保证了此时输出的刚好是字典序排第一的运送方法
for(int i = 0; i < 16; i++)
System.out.println(path[i].c + " "+ (path[i].x+1) + " " + (path[i].y+1));
}
return;
}
//遍历牧场
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++) {
if(!status[i][j] && check(c,i,j)) { //该处可以替换
//替换之
char t = g[i][j];
g[i][j] = c;
path[step] = new Triad(c,i,j);
status[i][j] = true;
num[c - 'A']--;
if(step == 15) dfs('N',16); //15时已经成功了,需要特判,否则ans会重复++
else {
//依次取一种小牛进行dfs
for(int k = 0; k < 5; k++)
if(num[k] > 0)
dfs((char)(k + 'A'), step+1);
}
//回溯时恢复现场
g[i][j] = t;
status[i][j] = false;
num[c - 'A']++;
}
}
return;
}
//检测
private static boolean check(char c, int x, int y) {
for(int i = x - 1; i <= x + 1; i++)
for(int j = y - 1; j <= y + 1; j++)
if(i >= 0 && i < 4 && j >= 0 && j < 4 && g[i][j] == c)
return false;
return true;
}
}
class Triad {
public char c;
public int x;
public int y;
public Triad(char c, int x, int y) {
this.c = c;
this.x = x;
this.y = y;
}
}