java - 验证战舰板，二维数组，如何检查板有效性的可能性？
问题描述
当给定一个包含 1 和 0 的二维数组时，用 Java 编写代码来验证战舰板，其中 1 是船的一部分，0 是海。以下是要了解的规则：
- 必须有单艘战舰（4格大小）、2艘巡洋舰（3号）、3艘驱逐舰（2号）和4艘潜艇（1号）。不允许任何额外的船只，以及丢失的船只。
-每艘船都必须是一条直线，潜艇除外，它只是一个单元格。
-船不能重叠，但可以与任何其他船接触。
我的方法只是计算尺寸 2 尺寸 3 尺寸 4 船舶的所有可能连接，并确保它们大于所需尺寸船舶的数量，这不适用于每种情况，我也会帮助检查是否有正好是 20 个位置，1 的问题是，如果我们有 0 1 1 1 1 0 0 0 0 0 它会告诉我它是有效的，尽管它绝对不是（因为它是一排和一艘船）当我有以下: 应该是假的，但我的返回真->
{0,0,0,0,0,0,0,1,1,0},
{0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,1,1,1,0},
{0,1,0,0,0,0,0,0,0,0},
{0,1,0,0,1,1,1,0,0,0},
{0,0,0,0,1,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,1,1,0},
{0,0,1,0,0,0,0,1,1,0},
或者应该是假的，但我的返回真->
{0,1,1,1,0,0,0,0,0,0},
{0,0,0,1,1,1,0,0,0,0},
{0,1,1,1,0,0,0,0,0,0},
{0,0,0,1,1,1,0,0,0,0},
{0,1,1,1,0,1,1,0,0,0},
{0,1,0,0,0,0,1,1,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
这是一个示例，当代码应该返回 true 时它可以工作：
{1,0,0,0,0,1,1,0,0,0},
{1,1,0,0,0,0,0,0,1,0},
{1,1,0,0,1,1,1,0,1,0},
{1,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,1,0},
{0,0,0,0,1,1,1,0,0,0},
{0,0,0,1,0,0,0,0,1,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,0,0,0},
但是当我有这个例子时：
{0,0,1,0,0,0,0,1,1,0},
{0,1,1,0,0,0,0,0,0,0},
{1,1,1,1,1,0,0,0,0,1},
{0,0,1,1,1,1,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,1,1,0,0,0,0,0,0,0},
{0,0,0,0,0,0,1,0,0,1},
{0,0,0,0,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
应该是假的，但我的代码返回真。所以我怎样才能找到一种方法来重组我的代码或有一个解决方案，当我得到一块板时，我真的不知道它是否有效。但我的Java程序会吗？
这是我为此尝试的代码，我的方法是列出检查特定船舶的所有变体，从最大到更小（最大将是 [4 3 3 2 2 2] 不包括 1，因为它会显着增加变化的数量，我可以以不同的方式更有效地检查它，最小的变化将是 [2 2 2 3 3 4] 4 最后重复它们的原因是因为对于 2 有 x3 船所以 2 2 2, x2 大小3 艘船所以 3 3 和 x1 尺寸 4 船所以只有一个）这里是代码：
import java.util.*;
class Permute{
public static List<int[]> l;
Permute(){
this.l=new ArrayList<int[]>();
}
static void permute(java.util.List<Integer> arr, int k){
for(int i = k; i < arr.size(); i++){
java.util.Collections.swap(arr, i, k);
permute(arr, k+1);
java.util.Collections.swap(arr, k, i);
}
if (k == arr.size() -1){
l.add(arr.stream()
.map(i -> (i == null ? 0 : i))
.mapToInt(Integer::intValue)
.toArray());
}
}
public static List<int[]> get(){
Permute.permute(java.util.Arrays.asList(2,2,2,3,3,4), 0);Collections.reverse(l);
return l;
}
}
public class BF {
private static int[][] fields,copy;
private static int[] ship= {0,0,3,2,1};
public BF(int[][] field) {
fields=field;
// print(field);
this.copy=field;
}
public boolean validate() {
int cnt=counter(fields);
if(cnt!=20)return false;
Permute p= new Permute();//permutation constructor
List<int[]> list=p.get();//gets our specific permution
for (int i = 0; i < list.size(); i++) {//run through each option of our permution list
copy=fields;
ship=new int[]{0,0,3,2,1};//amount of ships needed
boolean flag=check(fields,list.get(i));//checks if the permution variation is true or false
int cnt1=counter(copy);//we checked boats of size 2 3 4 but not 1 which means if its valid then there should be 4 boats left
if(flag && cnt1==4)return true;
}
return false;
}
public static boolean check(int[][] field,int[] ships){
for(int i=0;i<ships.length;i++) {//go through the array and loop through the variation
int num=getBoat(fields, ships[i]);//if the boat is true on the certain boat we are checking
ship[num]--;//then -1 and at the end we want it to be [<=0,0,0,0,0]
}
int counter=0;
for(int i=2;i<ship.length;i++) {
if(ship[i]==0)counter++;//if [0,0,0]
}
if(counter==3) {return true;}//then return true
return false;
}
public static int getBoat(int[][] field,int num) {
int dire=0,r=0,c=0;String dir="row";
for (int col = 0; col < fields[0].length; col++) {
for (int row = 0; row < fields.length; row++) {//loop through each coordinate
if (copy[row][col] == 1) {//check if its part of a boat at the coor
int length=field.length;dir="row";dire=row;
for(int j=0;j<2;j++) {//go horizontal then vertical
if(j==1) {length=field[0].length;dir="col";dire=col;}//change length to vertical
if(dire+num-1<length) {//make sure we don't get outofbounds error
int cnt=0;
for(int i=0;i<num;i++) {//checks each coor according to type of boat we are checking
if(dir.equals("row")) {r=row+i;c=col;}
else if(dir.equals("col")){r=row;c=col+i;}
if(copy[r][c]==1) {//check
cnt++;//copy of battle field becomes 0
}
else copy=fields;//otherwise break this loop since it is not relevant anymore on this coor
if(cnt==num) {
for(int k=0;k<num;k++) {
if(dir.equals("row")) {r=row+k;c=col;}
else if(dir.equals("col")){r=row;c=col+k;}
copy[r][c]=0;//now we know its valid length and make it 0 on the copy
}
return cnt;
}}}} //if num is correct then return it
}
}
}return 0;
}
public static int counter(int[][] f) {// counts amount of tiles on the board with 1's
int cnt=0;
for (int col = 0; col < f[0].length; col++) {
for (int row = 0; row < f.length; row++) {
if (f[row][col] == 1) {
cnt++;
}
}
}
return cnt;
}
public static void print(int[][] field) {//prints the board
for (int row = 0; row < field.length; row++) {
for (int col = 0; col < field[0].length; col++) {
if(col<field[0].length-1 && col!=0) {
System.out.print( field[row][col]+",");
}
else if(col==field[0].length-1){
System.out.print( field[row][col]+"},");
}
else if(col==0) {
System.out.print(" {"+ field[row][col]+",");
}
}
System.out.println("");
}
System.out.println("\n");
}
}
该代码现在似乎运行良好，但在假设的情况下不会返回 true。
以下是一些代码应返回 true 但返回 false 的示例：
{1,0,0,0,0,1,1,0,0,0},
{1,0,1,0,0,0,0,0,1,0},
{1,0,1,0,1,1,1,0,1,0},
{1,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,1,0},
{0,0,0,0,1,1,1,0,0,0},
{0,0,0,0,0,0,0,0,1,0},
{0,0,0,1,0,0,0,0,0,0},
{0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,0,0,0},
这里是真的：
{1,0,0,0,0,0,0,0,1,0},
{0,0,1,0,0,1,1,1,1,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,1,1,1,1,1,0,0,0},
{0,0,1,1,1,0,0,0,0,0},
{0,0,1,0,1,0,0,0,0,0},
{0,0,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
这里是真的：
{1,0,0,0,0,1,1,0,0,0},
{1,1,0,0,0,0,0,0,1,0},
{1,1,0,0,1,1,1,0,1,0},
{1,0,0,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,0,1,0},
{0,0,0,0,1,1,1,0,0,0},
{0,0,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,0,0,0},
这里是真的：
{1,1,1,0,0,0,0,0,0,0},
{1,1,0,0,0,0,0,0,1,0},
{1,1,0,0,1,1,1,0,1,0},
{1,0,0,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,0,1,0},
{0,0,0,0,1,1,1,0,0,0},
{0,0,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,0,0,0},
这里是真的：
{1,0,0,0,0,1,1,0,0,0},
{1,1,0,0,0,0,0,0,1,0},
{1,1,0,0,1,1,1,0,1,0},
{1,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,1,0},
{0,0,0,0,1,1,1,0,0,0},
{0,0,0,1,0,0,0,0,1,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,0,0,0},
但是代码在这些示例中返回 false
所以在这个例子中
{1,1,1,0,0,0,0,0,0,0},
{1,1,0,0,0,0,0,0,1,0},
{1,1,0,0,1,1,1,0,1,0},
{1,0,0,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,0,1,0},
{0,0,0,0,1,1,1,0,0,0},
{0,0,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,0,0,0},
它有效，因为：
[![在此处输入图像描述][1]][1]
但是我的代码采用第一个大小选项，这就是我的代码返回错误的情况-
[![在此处输入图像描述][2]][2]
那么我需要添加什么来解决这个问题？
public class BF {
private static int[][] fields;
public BF(int[][] field) {
fields=field;
print(field);
}
public boolean validate() {
int cnt=counter(fields);
if(cnt!=20)return false;
return checkBoard(fields, new int[]{4,3,3,2,2,2},0,new int[] {3,2,1});
}
public static boolean checkBoard(int[][] board,int[] SizePlacement,int k,int[] shipAmount){
if (counter(board)==4 ) {
return true;
}
int cnt=0;//SizePlacement={4,3,3,2,2,2}, ship(changes)={3,2,1}, k(starts at 0) is placement in ships[]
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board[0].length; col++) {
if(board[row][col]==1 && row+SizePlacement[k]<board.length) {//vertically
cnt=1;
for(int i=1;i<SizePlacement[k];i++) {//check vertically
if(board[row+i][col]==1) {cnt++;}
}
if(cnt>=SizePlacement[k]) {
int[][] newBoard = deepcopy(board);
newBoard= remove(newBoard , row, col, SizePlacement[k], "ver");
shipAmount[SizePlacement[k]-2]--;
if(shipAmount==new int[]{0,0,0}) {return true;}
if(k+1<SizePlacement.length && checkBoard(newBoard,SizePlacement,k+1,shipAmount)) {return true;}
shipAmount[SizePlacement[k]-2]++;
}
}
if(board[row][col]==1 && col+SizePlacement[k]<board[0].length) {//horizontally
cnt=1;
for(int i=1;i<SizePlacement[k];i++) {//check horizontally
if(board[row][col+i]==1) {cnt++;}
}
if(cnt>=SizePlacement[k]) {
int[][] newBoard = deepcopy(board);
newBoard= remove(newBoard , row, col, SizePlacement[k], "hor");
shipAmount[SizePlacement[k]-2]--;
if(shipAmount==new int[]{0,0,0}) {return true;}
if(k+1<SizePlacement.length &&checkBoard(newBoard,SizePlacement,k+1,shipAmount)) {
return true;
}
shipAmount[SizePlacement[k]-2]++;
}
}
}
}
return false;
}
public static int[][] remove(int[][] newBoard,int row,int col,int size,String orien){
int[][] removedBoard= deepcopy(newBoard);
if(orien=="ver") {
for(int i=0;i<size;i++) {
removedBoard[row+i][col]=0;
}
print(removedBoard);
return removedBoard;
}
else if(orien=="hor") {
for(int i=0;i<size;i++) {
removedBoard[row][col+i]=0;
}
print(removedBoard);
return removedBoard;
}
return removedBoard;
}
public static int[][] deepcopy(int[][] fields){
int[][] copy= new int[fields.length][fields[0].length];
for (int row = 0; row < fields.length; row++) {
for (int col = 0; col < fields[0].length; col++) {
copy[row][col]= fields[row][col];
}
}
return copy;
}
public static int counter(int[][] f) {// counts amount of tiles on the board with 1's
int cnt=0;
for (int col = 0; col < f[0].length; col++) {
for (int row = 0; row < f.length; row++) {
if (f[row][col] == 1) {
cnt++;
}
}
}
return cnt;
}
public static void print(int[][] field) {//prints the board
for (int row = 0; row < field.length; row++) {
for (int col = 0; col < field[0].length; col++) {
if(col<field[0].length-1 && col!=0) {
System.out.print( field[row][col]+",");
}
else if(col==field[0].length-1){
System.out.print( field[row][col]+"},");
}
else if(col==0) {
System.out.print(" {"+ field[row][col]+",");
}
}
System.out.println("");
}
System.out.println("\n");
}
}
这似乎有一些错误（与解决方案不同），不确定是否会对此提供帮助 [1]：https ://i.stack.imgur.com/bX32n.png [2]：https://i .stack.imgur.com/tFP1N.png
解决方案
如果所有船只的位置都有效，则该板有效。
这意味着您需要船舶的数据结构。首先，一个简单的数据结构可能是[ ship_type, [ position_1 , position_2, position_3 ] ]
一旦你有了船的数据结构，检查所有船都在棋盘上，没有两艘船共享一个位置，以及每种类型的船在棋盘上的正确数量是微不足道的。每种类型的正确船只数量可以进入Fleet数据结构。
有了一艘船，你很快就会意识到，可以用字母来为他们的船队提供船队意识的一方的董事会。但另一块板是“特殊的”，因为没有船舶能见度。这意味着（在真实游戏中）战舰由两种板组成，一个命中检测板和一个船舶定位板。它们看起来相似只是制造的副作用。
现在，HitBoard人工智能将如何尝试追捕一艘船？好吧，他们会从随机放置或模式开始。这两种方法都有优点。一旦检测到命中，它就会查询场地上剩余船只的数量，并开始沿水平和垂直轴探测以找到船只的完整位置。一旦它被告知“你击沉了我的”，它就会知道必须将沉没的船从游戏中移除。
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,1,1,1,1,0,0},
{0,0,0,0,1,1,1,1,0,0},
{0,0,0,0,1,1,1,1,0,0},
{0,0,0,0,1,1,1,1,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
由两艘战列舰、一艘驱逐舰、一艘潜艇和一艘巡洋舰组成。如果没有额外的信息，就不可能知道大多数船只是从左到右还是从上到下。
有时，在游戏进行时甚至无法知道船的位置。有趣的是，这可能并不总是足够的信息来了解船的位置。这种情况有时会发生在船只处于紧密排列的编队中时，并且您通过在已经记录命中的一排或一列（或两者）方格内进行攻击来击沉船只。在这种情况下，您的命中可能不会定义沉没项目的结束。
如果目标是在没有位置以外的任何额外信息的情况下验证董事会，那么您需要采取不同的方法。
- 按大小订购船只。
- 在当前的棋盘位置内，重复直到没有可用的船只。
- 选择最大的船。
- 搜索最大船舶的所有可能位置，生成没有船舶位置标记的新板。
- 如果无法放置船，则该板不是有效的板配置。
- 如果船列表为空且板上有标记，则该板不是有效的板配置。
- 如果船舶列表为空且板为空，则标记处于有效的板配置中。
- 重复，为步骤 2 中生成的电路板独立处理所有电路板。
这是一种蛮力方法；但是，在蛮力方法中有许多可能的优化。
推荐阅读
- docker - 如何使用通配符设置 docker 的 NO_PROXY
- ios - React Native JS bundle 在 iOS Release 上崩溃，Babel 不工作？
- scala - 通过使用 Levenshtein 算法与另一列中的现有数据进行比较来更新数据框列
- angularjs - 刷新页面删除非 URL $stateParam (ui-router)
- spring - JUNIT 5：将 spring 组件注入自定义 TestTemplateInvocationContextProvider
- java - 在 OAuth 2.0 中调用 REST http 方法补丁的 JAVA 代码
- java - 在我的应用程序上添加简单的 log4j
- perl - Perl 动态输入文件
- c++ - Json 序列化向量
到 json 数组 (nlohmann/json.hpp) - oracle - ORA-02199: 缺少 DATAFILE/TEMPFILE 子句