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;
    }
            
}


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


Помогите дорешать :)
  • Вопрос задан
  • 112 просмотров
Пригласить эксперта
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы