#java #puzzle
#java #Головоломка
Вопрос:
написание кода на Java для проверки доски линкора при задании 2d-массива с 1 и 0, где 1 — часть корабля, а 0 — море. вот правила, которые нужно знать:
-Должен быть один линкор (размер 4 клетки), 2 крейсера (размер 3), 3 эсминца (размер 2) и 4 подводные лодки (размер 1). Любые дополнительные корабли не допускаются, а также недостающие корабли.
-Каждый корабль должен быть прямой линией, за исключением подводных лодок, которые представляют собой всего лишь одну ячейку.
-Корабль не может пересекаться, но может контактировать с любым другим кораблем.
мой подход состоял в том, чтобы просто подсчитать все возможные соединения для кораблей размера 2, размера 3, размера 4 и убедиться, что они больше, чем требуемое количество кораблей размера, это работает не для каждого сценария, также я бы помог проверить, есть ли ровно 20 мест размещения с 1 проблема в том, что если у нас есть 0 1 1 1 1 0 0 0 0 0 он скажет мне, что он действителен, хотя это определенно не так (поскольку в нем одна строка и один корабль), и когда у меня будет следующее: должно быть false, но мое возвращает true->
{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},
или
который должен быть false, но мой возвращает true->
{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},
должно быть false, но мой код возвращает true. итак, как я могу найти способ реструктурировать свой код или найти решение, которое, когда мне дают плату, я бы на самом деле не знал, действительна она или нет. но моя 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 amp;amp; 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 amp;amp; 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");
}
}
the code seems to run well now but doesn’t return true when its suppose to.
here are some examples where the code should return true but returns 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},
true here:
{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},
true here:
{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},
true here:
{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},
and true here:
{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]
но мой код принимает первый вариант размера, и это то, что происходит, который мой код возвращает как false-
[! [введите описание изображения здесь] [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 amp;amp; 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 amp;amp; checkBoard(newBoard,SizePlacement,k 1,shipAmount)) {return true;}
shipAmount[SizePlacement[k]-2] ;
}
}
if(board[row][col]==1 amp;amp; 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 amp;amp;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 amp;amp; 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
Комментарии:
1. Не могли бы вы проверить каждую строку / столбец, чтобы увидеть, содержат ли они последовательные единицы, и если да, добавьте их в счетчик каждого корабля? В конце убедитесь, что каждый тип судна был подсчитан правильное количество раз.
2. Почему бы не пометить каждый корабль своим номером, например, 1 — линкор. 2,3 — крейсеры и т.д. Это может упростить проверку платы.
3. да, ты мог бы @AdrianRusso, но могут быть разные варианты, например, 111 — это размер 3 и размер2
4. @AlexRudenko я вроде как это сделал, я создал массив с именем num (думаю, я должен был назвать его ships), в котором хранятся числа — я сейчас его изменю)… так что да, я сделал
5. @Abra что ж, ваша программа должна рассмотреть все возможности и выяснить, является ли доска действительной. человек, который настраивает доску, не скажет вам, подводная лодка это или эсминец… Я понимаю ваше беспокойство, но я предпочитаю оставить его с 1 и 0
Ответ №1:
Поскольку мы не можем с уверенностью отличить корабли друг от друга, нам нужно будет попробовать разные варианты. Попробуйте поместить корабль в возможную позицию (зарезервировав эту позицию), а затем повторите попытку для следующего корабля рекурсивно. (Вероятно, это то, что предлагали и другие). Для платы 10х10 с таким количеством кораблей вычисления выполняются довольно быстро.
Вот моя попытка реализовать это.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;
import java.util.concurrent.atomic.AtomicInteger;
public class Main {
private static final int SIZE = 10;
private static final int HORIZONTAL = 0;
private static final int VERTICAL = 1;
private static final int[] shipSizes = {4, 3, 3, 2, 2, 2};
private static final int NR_OF_ONES = 4;
private static final int[][] board1 = {
{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}};
private static AtomicInteger counter = new AtomicInteger();
public static void main(String[] args) {
int[][] board = board1;
validateBoard(board);
long start = System.nanoTime();
boolean valid = checkBoard(board, 0);
long time = System.nanoTime() - start;
System.out.println("Board is " (valid ? "" : "NOT ") "valid");
System.out.println("Checked board in " time " ns");
}
private static boolean checkBoard(int[][] currentBoard, int shipSizePos) {
if (shipSizePos >= shipSizes.length) {
return true;
// return countOnes(currentBoard) == NR_OF_ONES;
}
List<Ship> currentSizeShips = findPossibleShips(currentBoard, shipSizes[shipSizePos]);
boolean valid = false;
for (Ship ship : currentSizeShips) {
if(checkBoard(removeShipFromBoard(currentBoard, ship), shipSizePos 1)) {
return true;
}
}
return valid;
}
private static int[][] removeShipFromBoard(int[][] board, Ship ship) {
int[][] newBoard = new int[SIZE][SIZE];
for (int r = 0; r < SIZE; r) {
for (int c = 0; c < SIZE; c) {
if ((ship.orientation == HORIZONTAL amp;amp; r == ship.row amp;amp; (c >= ship.col amp;amp; c < ship.col ship.size))
|| (ship.orientation == VERTICAL amp;amp; c == ship.col amp;amp; (r >= ship.row amp;amp; r < ship.row ship.size))) {
newBoard[r][c] = 0;
} else {
newBoard[r][c] = board[r][c];
}
}
}
return newBoard;
}
private static List<Ship> findPossibleShips(int[][] board, int size) {
List<Ship> ships = new ArrayList<>();
for (int r = 0; r < SIZE; r) {
for (int c = 0; c < SIZE; c) {
if (board[r][c] == 1) {
if (isPossibleHorizontalShip(board, size, r, c)) {
ships.add(new Ship(r, c, size, HORIZONTAL));
}
if (isPossibleVerticalShip(board, size, r, c)) {
ships.add(new Ship(r, c, size, VERTICAL));
}
}
}
}
return ships;
}
private static boolean isPossibleHorizontalShip(int[][] board, int size, int row, int col) {
if (SIZE - col < size) {
return false;
}
int c;
for (c = col; c < SIZE amp;amp; board[row][c] == 1; c) ;
return c - col >= size;
}
private static boolean isPossibleVerticalShip(int[][] board, int size, int row, int col) {
if (SIZE - row < size) {
return false;
}
int r;
for (r = row; r < SIZE amp;amp; board[r][col] == 1; r) ;
return r - row >= size;
}
private static int countOnes(int[][] board) {
int ones = 0;
for (int r = 0; r < SIZE; r) {
for (int c = 0; c < SIZE; c) {
ones = board[r][c];
}
}
return ones;
}
private static void validateBoard(int[][] board) {
for (int r = 0; r < SIZE; r) {
for (int c = 0; c < SIZE; c) {
if (!(board[r][c] == 0 || board[r][c] == 1)) {
throw new IllegalArgumentException("Illegal character at " r ", " c);
}
}
}
if (countOnes(board) != Arrays.stream(shipSizes).sum() NR_OF_ONES) {
throw new IllegalArgumentException("Wrong number of ship pieces");
}
}
private static class Ship {
private final int row;
private final int col;
private final int size;
private final int orientation;
public Ship(int row, int col, int size, int orientation) {
this.row = row;
this.col = col;
this.size = size;
this.orientation = orientation;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Ship ship = (Ship) o;
return row == ship.row amp;amp; col == ship.col amp;amp; size == ship.size amp;amp; orientation == ship.orientation;
}
@Override
public int hashCode() {
return Objects.hash(row, col, size, orientation);
}
@Override
public String toString() {
return "Ship{"
"row=" row
", col=" col
", size=" size
", orientation=" orientation
'}';
}
}
}
- Сначала проверяет плату, чтобы убедиться, что она содержит только 0 и 1, а также правильное количество 1
- Просматривает список кораблей, не относящихся к размеру 1, от самых больших до самых маленьких.
- Выполняет поиск возможных мест размещения для текущего размера, удаляет одно из них и проверяет эту ветку на наличие следующего размера
- Когда остается только 1 сек, плата в порядке (мы полагаемся на правильность подсчета при проверке)
Ответ №2:
Доска действительна, если позиция всех кораблей действительна.
Это означает, что вам нужна структура данных для корабля. Для начала простая структура данных может быть [ ship_type, [ position_1 , position_2, position_3 ] ]
Как только у вас есть структуры данных для корабля, тривиально проверить, что все корабли находятся на доске, никакие два корабля не занимают одну позицию и на доске находится правильное количество кораблей каждого типа. Правильное количество кораблей каждого типа может входить в Fleet структуру данных.
С кораблем вы быстро поймете, что доска для стороны с информацией о ее флоте может быть отображена буквами для их кораблей. Но другая плата «особенная», потому что нет видимости корабля. Это означает, что (как и в реальной игре) Battleship состоит из двух видов досок: доски для определения попадания и доски для определения местоположения корабля. То, что они выглядят одинаково, является лишь побочным эффектом производства.
Теперь о 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.
Это подход грубой силы; но в рамках подхода грубой силы возможен ряд оптимизаций.
Комментарии:
1. не знаю, как это сделать. у вас есть ссылка или статья, на которую я могу посмотреть, чтобы понять? спасибо.
2. Создание новой структуры данных в Java выполняется с помощью слов
public class Ship {Остальное зависит от того, как вы хотите представитьShip.3. мой вопрос не в том, чтобы играть в игру и что делать (хотя это полезно знать: P), когда задана плата (2d-массив), как я могу доказать, является ли она действительной или нет
4. Вы можете доказать, действительно ли это, полностью удалив метки в процедуре, описанной выше. Если все лодки можно убрать по одной, не оставив на доске никаких отметок, значит, вы «заполнили» отметки позициями лодок.
5. в значительной степени то, что я сделал, но это не работает. те, которые я использую для перестановок, чтобы получить все варианты порядка кораблей для проверки, такие как 4 3 3 2 2 2 или 3 4 3 2 2 2… затем код, но, похоже, он не работает на действительных кораблях, когда я запускаю код… (Я не включил 1,1,1,1, потому что это значительно увеличит возможности изменения) и просто проверьте это по-другому
Ответ №3:
Я думаю, что лучший способ подойти к этому — это итеративно размещать корабли, начиная с самых больших. Грубый набросок алгоритма таков:
- Выберите самый большой корабль, который не размещен
- Рассмотрите список всех возможных мест размещения
- Для каждого возможного размещения удалите эти единицы из массива и повторите процесс без корабля, который вы только что разместили
Поскольку вы не кодируете тип корабля, к которому относятся определенные точки, вы можете удалить точки с размещенных кораблей и продолжить попытки разместить корабли. Это будет взрываться по мере увеличения количества кораблей, но я думаю, что это достаточно быстро для этого небольшого решения.
Комментарии:
1. это то, что я сделал, но оно проходит через многие примеры, поэтому оно недостаточно хорошо. также я хочу проверить несколько плат одновременно. кроме того, в моем коде есть некоторые ошибки.
2. это в значительной степени мой подход, похоже, сейчас он работает, но я не уверен, почему мой код не работает.
Ответ №4:
Попытка решения, которое не допускает контакта:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
public class BattleFieldValidator {
private static final int SIZE = 10;
private static class Ship {
public int col;
public int row;
public boolean horizontal;
public int size;
@Override
public String toString() {
return "size " size " at (" (row 1) "," (col 1) ") " (horizontal ? "horizontal" : "vertical");
}
}
public static void validateField(int[][] field) {
// 10x10 field
if(field.length != SIZE || field[0].length != SIZE) {
throw new RuntimeException("invalid field dimensions");
}
// each cell 0 or 1
for(int row = 0; row < SIZE; row ) {
for(int col = 0; col < SIZE; col ) {
int cellValue = field[row][col];
if(cellValue != 0 amp;amp; cellValue != 1) {
throw new RuntimeException("invalid cell value at (" (row 1) "," (col 1) ")");
}
}
}
print(field);
boolean[][] discoveredShipCells = new boolean[SIZE][SIZE];
List<Ship> ships = new ArrayList<>();
for(int row = 0; row < SIZE; row ) {
for(int col = 0; col < SIZE; col ) {
if(discoveredShipCells[row][col]) {
continue;
}
if(field[row][col] == 1) {
Ship ship = discoverShip(field, discoveredShipCells, row, col);
ships.add(ship);
}
}
}
Collections.sort(ships, (a, b) -> b.size - a.size);
System.out.println("discovered ships:");
ships.forEach(s -> System.out.println(s));
if(ships.stream().filter(s -> s.size == 4).count() != 1) {
throw new RuntimeException("battleship(size 4) count != 1");
}
if(ships.stream().filter(s -> s.size == 3).count() != 2) {
throw new RuntimeException("cruiser(size 3) count != 2");
}
if(ships.stream().filter(s -> s.size == 2).count() != 3) {
throw new RuntimeException("destroyer(size 2) count != 3");
}
if(ships.stream().filter(s -> s.size == 1).count() != 4) {
throw new RuntimeException("submarine (size 1) count != 4");
}
// ok
}
private static Ship discoverShip(int[][] field, boolean[][] discoveredShipCells, int shipStartRow, int shipStartCol) {
Ship ship = new Ship();
ship.row = shipStartRow;
ship.col = shipStartCol;
int horizontalSize = 0;
for(int col = ship.col; col < SIZE amp;amp; field[ship.row][col] == 1; col ) {
horizontalSize ;
discoveredShipCells[ship.row][col] = true;
}
int verticalSize = 0;
for(int row = ship.row; row < SIZE amp;amp; field[row][ship.col] == 1; row ) {
verticalSize ;
discoveredShipCells[row][ship.col] = true;
}
if(horizontalSize > 1 amp;amp; verticalSize > 1) {
throw new RuntimeException("ship extending both horizontally and vertically at (" (ship.row 1) "," (ship.col 1) ")");
}
ship.horizontal = verticalSize == 1;
ship.size = ship.horizontal ? horizontalSize : verticalSize;
// validate ship surrounded by ocean cells
if(ship.horizontal) {
// left amp; right
validateOceanCell(ship, field, ship.row, ship.col - 1);
validateOceanCell(ship, field, ship.row, ship.col ship.size);
// top amp; bottom
for(int col = ship.col - 1; col <= ship.col ship.size; col ) {
validateOceanCell(ship, field, ship.row - 1, col);
validateOceanCell(ship, field, ship.row - 1, col);
}
}
else {
// top amp; bottom
validateOceanCell(ship, field, ship.row - 1, ship.col);
validateOceanCell(ship, field, ship.row ship.size, ship.col);
// left amp; right
for(int row = ship.row - 1; row <= ship.row ship.size; row ) {
validateOceanCell(ship, field, row, ship.col - 1);
validateOceanCell(ship, field, row, ship.col 1);
}
}
return ship;
}
private static void validateOceanCell(Ship ship, int[][] field, int row, int col) {
if(row < 0 || row >= SIZE || col < 0 || col >= SIZE) {
return /* outside field, ignore */;
}
if(field[row][col] == 1) {
throw new RuntimeException("ship " ship " not surrounded by whater at (" (row 1) "," (col 1) ")");
}
}
private static void print(int[][] field) {
System.out.println();
for(int row = 0; row < SIZE; row ) {
System.out.println(Arrays.stream(field[row]).boxed().collect(Collectors.toList()));
}
}
}
И минимальное тестирование:
public class BattleFieldTest {
@org.junit.Test
public void test1() {
int[][] battleField = { //
{ 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 } };
BattleFieldValidator.validateField(battleField);
}
@org.junit.Test
public void test2() {
int[][] battleField = { //
{ 0, 0, 0, 1, 0, 1, 0, 1, 0, 0 }, //
{ 0, 0, 0, 0, 0, 1, 0, 1, 0, 0 }, //
{ 0, 0, 1, 0, 0, 1, 0, 1, 0, 0 }, //
{ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 }, //
{ 1, 1, 0, 0, 1, 0, 0, 0, 0, 0 }, //
{ 0, 0, 0, 0, 0, 0, 0, 1, 1, 0 }, //
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 }, //
{ 0, 0, 0, 0, 0, 1, 0, 0, 1, 0 }, //
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 }, //
{ 0, 1, 1, 0, 0, 0, 0, 0, 0, 0 }, };
BattleFieldValidator.validateField(battleField);
}
}
Пример вывода:
[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]
discovered ships:
size 4 at (1,1) vertical
size 3 at (3,5) horizontal
size 3 at (6,5) horizontal
size 2 at (1,6) horizontal
size 2 at (2,3) vertical
size 2 at (2,9) vertical
size 1 at (5,9) horizontal
size 1 at (7,9) horizontal
size 1 at (8,4) horizontal
size 1 at (9,8) horizontal
Комментарии:
1. спасибо, хотя я уже пытался и решал проверку линкора без контакта, а остальные правила те же, так что мне это не нужно. плюс без контакта легче проверить, чем с контактом. хотя ваш код должен возвращать true / false, если плата действительна или нет!
2. Я написал этот код для вашего предыдущего вопроса. Вернуть логическое значение не сложно: попробуйте / перехватите весь метод проверки и верните false в случае исключения, true в противном случае. Было бы жаль, потому что вы потеряли бы всю приятную информацию об ошибках, которую вы могли бы показать пользователю.
Ответ №5:
Я думаю, @AlexRudenko имел в виду, что это будет легче проверить:
{0,0,0,0,0,0,0,2,2,0},
{0,0,0,0,0,0,0,3,3,3},
{0,0,0,0,0,4,4,4,4,0},
{0,2,0,0,0,0,0,0,1,0},
{0,2,0,0,3,3,3,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,2,0,0,0,0,2,1,0},
{0,0,2,0,0,0,0,2,1,0},