|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Konstantin Osmehin 2:5020/400 15 Mar 2002 13:31:47
To : Sergey Politov
Subject : Re: Поможите pls...
--------------------------------------------------------------------------------
а Вот поиск в ширину, он минимальный путь находит
#include <stdio.h>
FILE *fin,*fout;
int sX,sY,eX,eY,dim;
struct {int viewed,used;}matrix[50][50];
struct sTmp{int x,y,parent;void Set(int a, int b, int
c){x=a;y=b;parent=c;}}path[2500];
#define end if((path[pathCount-1].x==eX)&&(path[pathCount-1].y==eY)) return
1
int pathCount;
int findpath()
{
int left=0,right=0,x,y;
end;
do
{
right=pathCount;
for(int i=left;i<right;i++)
{
x=path[i].x;y=path[i].y;
if(((x-1)>=0)&&(!matrix[x-1][y].used)&&(!matrix[x-1][y].viewed))
path[pathCount++].Set(x-1,y,i);
end;
if(((x+1)<dim)&&(!matrix[x+1][y].used)&&(!matrix[x+1][y].viewed))
path[pathCount++].Set(x+1,y,i);
end;
if(((y-1)>=0)&&(!matrix[x][y-1].used)&&(!matrix[x][y-1].viewed))
path[pathCount++].Set(x,y-1,i);
end;
if(((y+1)<dim)&&(!matrix[x][y+1].used)&&(!matrix[x][y+1].viewed))
path[pathCount++].Set(x,y+1,i);
end;
}
left=right;
}while(left!=pathCount);
return 0;
}
void main()
{
fin=fopen("f.in","r");
fscanf(fin,"%d\n",&dim);
for(int i=0;i<dim;i++)
for(int j=0;j<dim;j++)
matrix[j][i].viewed=fscanf(fin,"%d",&matrix[j][i].used)-1;
fscanf(fin,"%d %d\n",&sX,&sY);
fscanf(fin,"%d %d\n",&eX,&eY);
fclose(fin);
fout=fopen("f.out","w");
path[0].Set(sX,sY,-1);
pathCount=1;
if(!findpath())
fprintf(fout,"Path not found\n");
else
{
int i=pathCount-1;
do
{
fprintf(fout,"(%d,%d)\n",path[i].x,path[i].y);
i=path[i].parent;
}
while(i!=-1);
}
fclose(fout);
}
вход:
3
0 0 0
0 1 0
0 0 0
0 0
1 2
выход
(1,2)
(0,2)
(0,1)
(0,0)
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.Mail.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Поможите pls... 