Урок 11. Метод IsPath / Lines / Примеры разработки
Игра Lines (Visual C++. MFC) Урок 11. Метод IsPath
На этом уроке мы добавим в наше программу метод IsPath класса CLinesDoc. Он имеет тип bool и отвечает на вопрос, есть ли путь между двумя некоторыми клеточками, или его нет.
Добавьте в класс CLinesDoc заготовку для нашего метода. Прототип у неё следующий:
bool IsPath(int xFrom, int yFrom, int xTo, int yTo);
В полученную заготовку вставьте следующий код:
bool CLinesDoc::IsPath(int xFrom, int yFrom, int xTo, int yTo)
{
bool bPathIsFound=false;
int iField[iNumOfRows][iNumOfRows];
for(int j=0;j<iNumOfRows;j++){
for(int i=0;i<iNumOfRows;i++){
iField[i][j]=m_field[i][j];
}
}
int iMaxPathLength=iNumOfRows*iNumOfRows+1;
iField[xFrom][yFrom]=-1;//начальная точка
iField[xTo][yTo]=iMaxPathLength;//конечная точкаint iNextSearch=-1;
bool bContSearch = true;
while(bContSearch){
bContSearch=false;
for(j=0;j<iNumOfRows;j++){
for(int i=0;i<iNumOfRows;i++){
//найдно очередное поле для перемещения.if(iField[i][j]==iNextSearch){
//начинаем обследовать его соседей//поле располжено слеваbool bIsLeft=(i==0);
//поле располжено справаbool bIsRight=(i==(iNumOfRows-1));
//поле располжено сверхуbool bIsTop=(j==0);
//поле располжено снизуbool bIsButtom=(j==(iNumOfRows-1));
if(!bIsLeft){
//если это искомое поле.if(iField[i-1][j]==iMaxPathLength){
bPathIsFound=true;
return bPathIsFound;
}
if(iField[i-1][j]==0){//если поле слева свободно
iField[i-1][j]=iNextSearch-1;
bContSearch = true;
}
}
if(!bIsRight){
//если это искомое полеif(iField[i+1][j]==iMaxPathLength){
bPathIsFound=true;
return bPathIsFound;
}
//если поле справа свободноif(iField[i+1][j]==0){
iField[i+1][j]=iNextSearch-1;
bContSearch = true;
}
}
if(!bIsTop){
//если это искомое поле.if(iField[i][j-1]==iMaxPathLength){
bPathIsFound=true;
return bPathIsFound;
}
//если поле сверху свободноif(iField[i][j-1]==0){
iField[i][j-1]=iNextSearch-1;
bContSearch = true;
}
}
if(!bIsButtom){
//если это искомое полеif(iField[i][j+1]==iMaxPathLength){
bPathIsFound=true;
return bPathIsFound;
}
//если поле снизу свободноif(iField[i][j+1]==0){
iField[i][j+1]=iNextSearch-1;
bContSearch = true;
}
}
}
}
}
iNextSearch--;
};
return bPathIsFound;
}
Теперь внесите небольшие изменения в метод OnLButtonUp класса CLinesView. Для этого найдите следующую строку:
Запускайте программу. Теперь при перемещении путь будет искаться правильно - если он есть, то шарик будет перемещаться, а если нет, то шарик перемещаться не будет.
При желанни можете разобраться с алгоритмим поиска пути. Его неофицальное название - метод водопроводчика. Приблизительно он работает так - в той клетке, откуда вы двигаетесь, вы открываете водопроводный кран, и смотрите, дойдет вода до нужной вам клетки или нет.