BenKenobi3
@BenKenobi3
Прусь с геймдева и IOT

Как реализовать поиск в ширину в Java для решения задачи «Путь коня»?

Существует задача: 5c23ff480895a999446402.jpeg

Как правильно её решить на Java?

У меня есть заготовка кода:
package newjavaapplication;

import java.io.IOException;
import java.nio.charset.Charset;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class NewJavaApplication {
    
    static String[][] m;
    static ArrayDeque<Element> graphQueue = new ArrayDeque();
    static Element start;
    static Element finish;
    
    public static void main(String[] args) throws IOException 
    {
        
        List<String> lines = Files.readAllLines(Paths.get("D:\\Max\\java\\NewJavaApplication\\src\\knightw.in"), Charset.defaultCharset());
        
        int N = lines.size();
        m = new String[N][N];
                
        for (int i = 0; i < N; i++){
            m[i]= lines.get(i).split(" ");
        }
        
        
        boolean f = true;
        
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
                
                if ("@".equals(m[i][j]))
                {      
                    if (f) 
                    {
                        m[i][j] = "S";       
                        start = new Element(i,j, new ArrayList());
                        f = false;
                    }
                    else
                    {
                        m[i][j] = "F";
                        finish = new Element(i,j, new ArrayList());
                    }
                }

        }              
        
        graphQueue.add(start);
        
        while(!graphQueue.isEmpty()){
        
            Element current = graphQueue.remove();
            
            int x = current.x;
            int y = current.y;
            
            ArrayList<int[]> way = current.way;
  
            for (int i = -2; i <= 2; i++)
                for (int j = -2; j <= 2; j++)
                    if (i * i + j * j == 5)
                    {

                        if (x+i == finish.x && y+j == finish.y)
                            System.out.println(way.size());
                        else 
                        if ( 0 <= x + i && x + i < N
                            && 0 <= y + j && y + j < N
                            && ".".equals(m[x + i][y + j]))
                        {
                            m[x + i][y + j] = "1";
                            
                            ArrayList<int[]> nowWay = way;
                            int[] nowInt = {x+i, y+j};
                            nowWay.add(nowInt);
                            
                            graphQueue.add(new Element(x + i, y + j, nowWay));
                        }
                        
                    }
            
        }
        
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
                System.out.print(m[i][j] + "\t");
            System.out.println();
        }           
    }
       
}


Где класс Element:
package newjavaapplication;

import java.util.ArrayList;

public class Element {
    
    int x;
    int y;
    
    ArrayList<int[]> way;

    public Element(int x, int y, ArrayList<int[]> way) {
        this.x = x;
        this.y = y;
        this.way = way;
    }
            
}


Используемый для тестирования файл доски:
@ . . . .
. . . . .
. . . . .
. . . . .
. . . . @


Помогите дорешать :)
  • Вопрос задан
  • 72 просмотра
Пригласить эксперта
Ответы на вопрос 1
longclaps
@longclaps
Хех, ты втихаря исправил условие, я и не заметил )
while (!graphQueue.isEmpty()) {
    Element current = graphQueue.remove();
    int x = current.x;
    int y = current.y;
    ArrayList<int[]> way = current.way;
    for (int i = -2; i <= 2; i++)
        for (int j = -2; j <= 2; j++)
            if (i * i + j * j == 5) {
                if (x + i == finish.x && y + j == finish.y) {
                    System.out.println(way.size() + 1);
                    for (int[] xy : way) {
                        m[xy[0]][xy[1]] = "@"; // омерзительно
                    }
                    for (i = 0; i < N; i++) {
                        for (j = 0; j < N; j++)
                            System.out.print(m[i][j] + "\t");
                        System.out.println();
                    }
                    System.exit(0);
                } else if (0 <= x + i && x + i < N
                        && 0 <= y + j && y + j < N
                        && ".".equals(m[x + i][y + j])) {
                    m[x + i][y + j] = "1";
                    //ArrayList<int[]> nowWay = way; // так нельзя, разбирайся с mutable
                    ArrayList<int[]> nowWay = (ArrayList<int[]>) way.clone();
                    int[] nowInt = {x + i, y + j};
                    nowWay.add(nowInt);
                    graphQueue.add(new Element(x + i, y + j, nowWay));
                }
            }
}
System.out.println("Невозможно");
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через TM ID
Похожие вопросы
BostonGene Москва
от 100 000 до 200 000 руб.
Digital Horizon Москва
от 150 000 руб.
Sidenis Томск
До 170 000 руб.
20 янв. 2019, в 22:33
30000 руб./за проект
20 янв. 2019, в 22:03
1000 руб./за проект