Fare ve Labirent Algoritmaları - (Stack & Queue)
Fare ve labirent problemleri, bilgisayar yazılımlarıyla çözülmesi için geliştirilmiş, çeşitli boyutlarda verilen haritalardan ve başlangıç noktasından oluşan, en kısa yoldan ve en kısa zamanda farenin labirentten çıkmasını sağlamanızı isteyen problemlerdir.
Labirentin çeşidine göre çıkış algoritmanız farkı olmak zorundadır. Burada Stack (Yığın) ve Queue (Sıra) algoritmalarından biraz bahsedeceğiz.
Problem çözümünde en kısa yolu bulmanız için, aynı Şehirlerarası Elektrik Aktarım algoritmasında izlediğimiz yol gibi en kısa yolu bulmak zorundayız. Burada haritamızın yapısına göre farklı yollar deneyebiliriz.
Örneğin, haritamızdaki uzun sapma olmayan koridorlar varsa sürekli ilerlememiz bizim için daha yararlı olacaktır. Fakat yollarımız sürekli dallanıp budaklanıyorsa, sağa ve sola sapan yolları kontrol etmek, çıkmaz yola girdiğimizde bir önceki başarılı girişimize kadar geri gitmemiz gerekmektedir. Düz koridorların çok olduğu bir haritada fare, sapmadan yolları izlemesi dahilinde daha çabuk çıkış noktasını bulacaktır. İşte Queue Data Diagramı ile çözülmüş bir harita ve kaynak kodu :
Labirentin çeşidine göre çıkış algoritmanız farkı olmak zorundadır. Burada Stack (Yığın) ve Queue (Sıra) algoritmalarından biraz bahsedeceğiz.
Problem çözümünde en kısa yolu bulmanız için, aynı Şehirlerarası Elektrik Aktarım algoritmasında izlediğimiz yol gibi en kısa yolu bulmak zorundayız. Burada haritamızın yapısına göre farklı yollar deneyebiliriz.
Örneğin, haritamızdaki uzun sapma olmayan koridorlar varsa sürekli ilerlememiz bizim için daha yararlı olacaktır. Fakat yollarımız sürekli dallanıp budaklanıyorsa, sağa ve sola sapan yolları kontrol etmek, çıkmaz yola girdiğimizde bir önceki başarılı girişimize kadar geri gitmemiz gerekmektedir. Düz koridorların çok olduğu bir haritada fare, sapmadan yolları izlemesi dahilinde daha çabuk çıkış noktasını bulacaktır. İşte Queue Data Diagramı ile çözülmüş bir harita ve kaynak kodu :
Örnek 70x70 Boyutunda Bir Harita
Kaynak Kodu - Queue Data Diagram
//C++ Programming Language
// zafercavdar
#include <stdlib.h>
#include <stdio.h>
FILE *inputf=fopen ("labirent.in","r");
FILE *outputf=fopen ("labirent.out","w");
char labirent[10000][10000];
int boyutx,boyuty,cozum[10000][10000],retX,retY,queue[1000000][2],tail=0,head=0;
void push(int x , int y)
{
queue[tail][0]=x;
queue[tail++][1]=y;
}
void pop()
{
retX= queue[head][0];
retY= queue[head][1];
head++;
}
void oku()
{
fscanf(inputf,"%d %d",&boyutx,&boyuty);
for (int i=0;i<=boyutx-1;i++)
for (int j=0;j<=boyuty-1;j++)
fscanf(inputf," %c",&labirent[i][j]);
}
void cozumolusturma()
{
for (int i=0;i<boyutx;i++)
for (int j=0;j<boyuty;j++)
cozum[i][j]=-1;
}
int komsuuretmeozel(int x1 , int y1 , int x2 , int y2)
{
if (labirent[x2][y2]=='.' && cozum[x2][y2]==-1)
{
cozum[x2][y2]=cozum[x1][y1]+1;
push(x2,y2);
if (x2==0 || y2==0 || x2==boyutx-1 || y2==boyuty-1)
{
fprintf(outputf,"En kisa yol : %d\n",cozum[x2][y2]);
fclose(inputf);
fclose(outputf);
exit(0);
}
}
return 0;
}
int komsuuret(int x, int y)
{
komsuuretmeozel(x,y,x+1,y);
komsuuretmeozel(x,y,x-1,y);
komsuuretmeozel(x,y,x,y+1);
komsuuretmeozel(x,y,x,y-1);
return 0;
}
int queueisempty()
{
return head==tail;
}
void BFS()
{
int i,j;
for (i=0;i<boyutx;i++)
for (j=0;j<boyuty;j++)
if (labirent[i][j]=='F')
{
cozum[i][j]=0;
push(i,j);
}
while (!queueisempty())
{
pop();
komsuuret(retX,retY);
}
}
int main()
{
oku();
cozumolusturma();
BFS();
return 0;
}
// zafercavdar
#include <stdlib.h>
#include <stdio.h>
FILE *inputf=fopen ("labirent.in","r");
FILE *outputf=fopen ("labirent.out","w");
char labirent[10000][10000];
int boyutx,boyuty,cozum[10000][10000],retX,retY,queue[1000000][2],tail=0,head=0;
void push(int x , int y)
{
queue[tail][0]=x;
queue[tail++][1]=y;
}
void pop()
{
retX= queue[head][0];
retY= queue[head][1];
head++;
}
void oku()
{
fscanf(inputf,"%d %d",&boyutx,&boyuty);
for (int i=0;i<=boyutx-1;i++)
for (int j=0;j<=boyuty-1;j++)
fscanf(inputf," %c",&labirent[i][j]);
}
void cozumolusturma()
{
for (int i=0;i<boyutx;i++)
for (int j=0;j<boyuty;j++)
cozum[i][j]=-1;
}
int komsuuretmeozel(int x1 , int y1 , int x2 , int y2)
{
if (labirent[x2][y2]=='.' && cozum[x2][y2]==-1)
{
cozum[x2][y2]=cozum[x1][y1]+1;
push(x2,y2);
if (x2==0 || y2==0 || x2==boyutx-1 || y2==boyuty-1)
{
fprintf(outputf,"En kisa yol : %d\n",cozum[x2][y2]);
fclose(inputf);
fclose(outputf);
exit(0);
}
}
return 0;
}
int komsuuret(int x, int y)
{
komsuuretmeozel(x,y,x+1,y);
komsuuretmeozel(x,y,x-1,y);
komsuuretmeozel(x,y,x,y+1);
komsuuretmeozel(x,y,x,y-1);
return 0;
}
int queueisempty()
{
return head==tail;
}
void BFS()
{
int i,j;
for (i=0;i<boyutx;i++)
for (j=0;j<boyuty;j++)
if (labirent[i][j]=='F')
{
cozum[i][j]=0;
push(i,j);
}
while (!queueisempty())
{
pop();
komsuuret(retX,retY);
}
}
int main()
{
oku();
cozumolusturma();
BFS();
return 0;
}