狼羊白菜问题

狼羊白菜问题

  public static void main(String[] args) {int arr[] = {0, 0, 0, 0};ArrayList<String> strings = new ArrayList<>();strings.add(Arrays.toString(arr));solution(arr, strings);}public static void solution(int[] arr, List<String> path) {for (int i = 0; i < arr.length - 1; i++) {if (arr[arr.length - 1] == 1) {arr[arr.length - 1] = 0;for (int k = 0; k < arr.length - 1; k++) {if (arr[k] == 1) {if (isValid(arr, path)) {path.add(Arrays.toString(arr));solution(arr, path);path.remove(path.size() - 1);}arr[k] = 0;if (isValid(arr, path)) {path.add(Arrays.toString(arr));solution(arr, path);path.remove(path.size() - 1);} else {arr[k] = 1;}}}} else {if (arr[i] == 1) {continue;}arr[arr.length - 1] = 1;arr[i] = 1;if (!isValid(arr, path)) {arr[arr.length - 1] = 0;arr[i] = 0;continue;}path.add(Arrays.toString(arr));if (isEnd(arr)) {System.out.println(Arrays.toString(path.toArray()));return;}solution(arr, path);path.remove(path.size() - 1);arr[i] = 0;}}}public static boolean isEnd(int[] arr) {for (int i = 0; i < arr.length; i++) {if (arr[i] != 1) {return false;}}return true;}public static boolean isValid(int[] arr, List path) {int com = 0;if (arr[arr.length - 1] == 0) {com = 1;}for (int i = 0; i < arr.length - 2; i++) {if (arr[i] == arr[i + 1] && arr[i] == com) {return false;}}return path.indexOf(Arrays.toString(arr)) == -1 ? true : false;}

结果
[[0, 0, 0, 0], [0, 1, 0, 1], [0, 1, 0, 0], [1, 1, 0, 1], [1, 0, 0, 0], [1, 0, 1, 1], [1, 0, 1, 0], [1, 1, 1, 1]]
[[0, 0, 0, 0], [0, 1, 0, 1], [0, 1, 0, 0], [0, 1, 1, 1], [0, 0, 1, 0], [1, 0, 1, 1], [1, 0, 1, 0], [1, 1, 1, 1]]

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！