Embedded Files
The Mouse and Cheese Question and Its Solution
We all remember the mazes filled with complicated paths and walls, challenging yet fun to solve. In some, the goal is to find a way out, while in others, it's to reach a specific target within the maze. To reach the target, we try many paths, consider all possibilities, and decide where to go. Sometimes, we even choose the shortest path. However, finding your way out of these mazes might not be as quick as it first appears. We're familiar with a device that can help with this, one that many of us have at home and spend approximately 2-3 hours in front of daily: the computer. Although we don't always use this machine for scientific purposes, its use in scientific fields is undeniable. Olympiads are one such area. As computer olympiad participants, we wanted to give you an example of the type of problem we solve at the olympiads. The task is to guide a mouse through a maze to the cheese using the shortest possible route.
The rules of the problem are as follows:
The mouse cannot leave the maze.
The mouse cannot pass through or jump over walls.
The mouse can move in four directions: north, south, east, and west.
The maze boundaries are: N rows by M columns, with NxM < 10000x10000.
Although there are many ways to solve this problem, three methods are particularly popular.
SOLUTION 1
Solving with the Help of Dynamite:
This approach eliminates the need for a computer.
SOLUTION 2
The Solution with STACK:
The FILO (First In Last Out) principle, also known as stack logic, operates on the idea of the last item added being the first to be removed. The term "stack" refers to a pile or collection arranged on top of each other, much like a stack of boxes. When we need to take a box, we take it from the top; similarly, when adding a box, we place it on top of the stack.
This data structure can be used to solve the mouse and cheese problem in the following way: We start from our current position and check the possible directions we can move in (right, left, up, down), taking into account walls and whether or not we are moving outside of the maze, etc. We then place these options into a stack data structure. Next, we take the top movement option from the stack, move the mouse to the new position, and again check for new possible movement options from this new location, adding them to the stack as well. This process is repeated until the cheese is reached.
SOLUTION 3:
Using the Queue Data Structure to Solve:
The queue data structure operates on the FIFO (First In First Out) principle, which means the first item to enter the queue is the first one to be removed. The term "queue" refers to a line or sequence resembling a queue of people or items. As illustrated, in a queue, the first item to join the line is the first one to leave. Anyone wishing to join the queue does so from the back.
To apply this concept to solving the mouse and cheese problem, you can use a queue to keep track of all possible paths the mouse can take, starting from its current location. Here's how it can work:
1. From the mouse's starting position, examine all possible directions it can move (north, south, east, west) that do not lead into walls or outside the maze.
2. Add these possible movements to the queue, indicating the mouse's next positions.
3. Remove the first position from the queue to decide the mouse's next move, then repeat the process from this new position—checking for possible movements, adding them to the queue, and so on.
4. Continue this process until the cheese is reached. The use of a queue ensures that you explore paths in the order they are discovered, effectively performing a breadth-first search (BFS) of the maze. This approach can efficiently find the shortest path to the cheese, assuming one exists, by exploring all possible paths in a systematic way.
The queue data structure is more efficient for this problem than the stack data structure because it operates faster and consumes fewer system resources. By scanning the maze, that is, as the mouse continuously branches out in all four alternative directions, the queue finds the cheese in a shorter period. Once the cheese is reached, the need to restart from a different path is eliminated since all alternative paths have been tried. The downside of using the stack data structure is that when the cheese is reached for the first time, not all paths have been scanned, which requires going back and repeating the process of finding the cheese through alternative paths.
Let's now examine a code written in the C programming language that finds the shortest path for the mouse in the given maze structure to reach the cheese:
/*Okuma fonksiyonunda duvarlar -1, yollar 0 olarak matrise atılıyor*/
void Oku(void)
{
int i,j;
oku=fopen("fare.in","r");
yaz=fopen("fare.out","w");
fscanf(oku,"%d %d",&N,&M);
fscanf(oku,"%d %d",&fx,&fy);
fscanf(oku,"%d %d",&px,&py);
fx--;fy--;px--;py--;/*fx fy=farenin konumu px py=peynirin konumu*/
for(i=0;i<N;i++)
{
for(j=0;j<M;j++)
{
fscanf(oku,"%d",&lab[i][j]);
if(lab[i][j])
lab[i][j]=-1;
}
}
}
/*Bu fonksiyon ana fonksiyonumuz.İlk başta Stack boşmu, yani gidebileceğimiz başka alternatif yer kaldı mı diye bakıyoruz.Eğer varsa bir daha Kontrol fonksiyonunu çağırıyoruz.Al() fonksiyonunda ise Stack'in en üstündeki koordinatlar a ve b değişkenlerine veriliyor.Fonksiyondan geri döndüğümüzde ise yeni yerimiz a ve b nin koordinatları oluyor.*/
void Yap(int x,int yEmbargo)
{
while(1)
{
Kontrol(x,y);
if(bas==son && stack[0][0]==0 && stack[0][1]==0)
return;
Al();
x=a;
y=b;
}
}
/*Farenin hangi yönlere gidebileceğini hesaplayan fonksiyon.Bu fonksiyonda dört yönü kontrol edip (labirentten taşıp taşmadığımız ve duvarlar),ardından ekle() fonksiyonu ile bulduğumuz yönleri Queue veri yapısına ekliyoruz*/
void Kontrol(int x,int y)
{
{
if(lab[x+1][y]==0 || lab[x+1][y]>lab[x][y]+1)
{
lab[x+1][y]=lab[x][y]+1;
ekle(x+1,y);
}
}
if(x-1>=0 && lab[x-1][y]!=-1)
{
if(lab[x-1][y]==0 || lab[x-1][y]>lab[x][y]+1)
{
lab[x-1][y]=lab[x][y]+1;
ekle(x-1,y);
}
}
if(y-1>=0 && lab[x][y-1]!=-1)
{
if(lab[x][y-1]==0 || lab[x][y-1]>lab[x][y]+1)
{
lab[x][y-1]=lab[x][y]+1;
ekle(x,y-1);
}
}
if(y+1<M && lab[x][y+1]!=-1)
{
if(lab[x][y+1]==0 || lab[x][y+1]>lab[x][y]+1)
{
lab[x][y+1]=lab[x][y]+1;
ekle(x,y+1);
}
}
}
Bazı deneysel sonuçlar:
Bu üç yolu da deneyip fareyi peynire ulaştıramadıysanız aşağıdaki gibi bir durum ortaya çıkabilir...
Page updated
Google Sites
Report abuse