Итак, я реализовал решение проблемы, которая началась с того, что я дал вам сетку (n,n). Мне потребовалось начать с (1,1), посетить определенные точки в сетке, отмеченные *, а затем, наконец, перейти к (n,n). Гарантируется, что размер сетки не превышает 15, а количество точек для посещения * гарантировано >=0 и ‹=n-2. Начальная и конечная точки всегда пусты. Есть определенные препятствия, # на которые я не могу наступить. Кроме того, если я посетил точку до достижения определенного *, я могу пройти его снова после сбора *.
Вот что делает мое решение. Я создал структуру данных под названием «Узел», которая имеет 2 целочисленных типа данных (x, y). Это в основном кортеж.
class Node
{
int x,y;
Node(int x1,int y1)
{
x=x1;
y=y1;
}
}
Принимая сетку, я поддерживаю набор, в котором хранятся координаты «*» в сетке.
Set<Node> points=new HashSet<Node>();
Я поддерживаю массив сетки, а также массив расстояний
char [][]
int distances [][]
Теперь я применяю BFS как (1,1) в качестве источника. Как только я встречаю какой-либо '*' (который, как я полагаю, будет самым близким, потому что BFS предоставляет нам кратчайший путь в невзвешенном графе), я удаляю его из набора.
Теперь я снова применяю BFS, где мой источник становится последней найденной координатой «*». Каждый раз я обновляю массив расстояний, так как моя исходная координата изменилась. Для массива сетки я обновляю пути, отмеченные как «V» (посещенные) для предыдущей итерации.
Весь этот процесс продолжается до тех пор, пока я не достигну последней «*». Кстати, если мой BFS возвращает -1, программа печатает "-1" и завершает работу.
Теперь, если я успешно достиг всех '' кратчайшим возможным путем (я думаю?), я устанавливаю координату (n, n) в сетке как '' и применяю BFS в последний раз. Так я доберусь до финальной точки.
Теперь мое решение, похоже, где-то терпит неудачу. Где-то ошибся? Моя концепция неверна? Этот «жадный» подход не работает? Получение кратчайшего пути между всеми контрольными точками '*' должно в конечном итоге дать мне кратчайший путь IMO.
Я огляделся и увидел, что эта проблема похожа на проблему коммивояжера, а также может быть решена с помощью динамического программирования и смеси DFS или алгоритма A *. Я понятия не имею, как это сделать. Кто-то даже сказал dijkstra между каждым *, но, насколько мне известно, в невзвешенном графе Dijktra и BFS работают одинаково. Я просто хочу знать, почему это решение BFS не работает
Наконец, вот мой код:
import java.io.*;
import java.util.*;
/**
* Created by Shreyans on 5/2/2015 at 2:29 PM using IntelliJ IDEA (Fast IO Template)
*/
//ADD PUBLIC FOR CF,TC
class Node
{
int x,y;
Node(int x1,int y1)
{
x=x1;
y=y1;
}
}
class N1
{
//Datastructures and Datatypes used
static char grid[][];
static int distances[][];
static int r=0,c=0,s1=0,s2=0,f1=0,f2=0;
static int dx[]={1,-1,0,0};
static int dy[]={0,0,-1,1};
static Set<Node> points=new HashSet<Node>();
static int flag=1;
public static void main(String[] args) throws IOException
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();//testcases
for(int ixx=0;ixx<t;ixx++)
{
flag=1;
r=sc.nextInt();
if(r==1)
{
sc.next();//Taking in '.' basically
System.out.println("0");//Already there
continue;
}
c=r;//Rows guarenteed to be same as rows. It a nxn grid
grid=new char[r][c];
distances=new int[r][c];
points.clear();
for(int i=0;i<r;i++)
{
char[]x1=sc.next().toCharArray();
for(int j=0;j<c;j++)
{
grid[i][j]=x1[j];
if(x1[j]=='*')
{
points.add(new Node(i,j));
}
}
}//built grid
s1=s2=0;
distances[s1][s2]=0;//for 0,0
int ansd=0;
while(!points.isEmpty())
{
for(int i=0;i<r;i++)
{
for (int j = 0; j < c; j++)
{
distances[i][j]=0;
if(grid[i][j]=='V')//Visited
{
grid[i][j]='.';
}
}
}
distances[s1][s2]=0;
int dis=BFS();
if(dis!=-1)
{
ansd += dis;//Adding on (minimum?) distaces
//System.out.println("CURR DIS: "+ansd);
}
else
{
System.out.println("-1");
flag = 0;
break;
}
}
if(flag==1)
{
for(int i11=0;i11<r;i11++)
{
for(int j1=0;j1<c;j1++)
{
if(grid[i11][j1]=='V')//These pnts become accesible in the next iteration again
{
grid[i11][j1]='.';
}
distances[i11][j1]=0;
}
}
f1=r-1;f2=c-1;
grid[f1][f2]='*';
int x=BFS();
if(x!=-1)
{
System.out.println((ansd+x));//Final distance
}
else
{
System.out.println("-1");//Not possible
}
}
}
}
public static int BFS()
{
// Printing current grid correctly according to concept
System.out.println("SOURCE IS:"+(s1+1)+","+(s2+1));
for(int i2=0;i2<r;i2++)
{
for (int j1 = 0; j1 < c; j1++)
{
{
System.out.print(grid[i2][j1]);
}
}
System.out.println();
}
Queue<Node>q=new LinkedList<Node>();
q.add(new Node(s1,s2));
while(!q.isEmpty())
{
Node p=q.poll();
for(int i=0;i<4;i++)
{
if(((p.x+dx[i]>=0)&&(p.x+dx[i]<r))&&((p.y+dy[i]>=0)&&(p.y+dy[i]<c))&&(grid[p.x+dx[i]][p.y+dy[i]]!='#'))
{//If point is in range
int cx,cy;
cx=p.x+dx[i];
cy=p.y+dy[i];
distances[cx][cy]=distances[p.x][p.y]+1;//Distances
if(grid[cx][cy]=='*')//destination
{
for(Node rm:points)// finding the node and removing it
{
if(rm.x==cx&&rm.y==cy)
{
points.remove(rm);
break;
}
}
grid[cx][cy]='.';//It i walkable again
s1=cx;s2=cy;//next source set
return distances[cx][cy];
}
else if(grid[cx][cy]=='.')//Normal tile. Now setting to visited
{
grid[cx][cy]='V';//Adding to visited
q.add(new Node(cx,cy));
}
}
}
}
return -1;
}
}
Вот мой код в действии для нескольких тестовых случаев. Дает правильный ответ:
JAVA: http://ideone.com/qoE859
Вот где мой код не работает: http://www.codechef.com/status/N1,bholagabbar< /а>
