Технологии Программирования. 8 лекция
.pdflabirint [x1][y1] = -1; // помечаем клетку как пройденную
FIFO[0][0]=x1; FIFO[1][0]=y1; //
FIFO[2][0]=0;
/* Начальные значения указателей очереди */
Start=0; Last=1;
/* на первом шаге начальные координаты фишки занесены в очередь в позицию 0, а следующий элемент будет 1 */
/* Все основные операции выполняет цикл, который
выполняется до тех пор, пока не будет достигнута клетка
(x2,y2)
*/
while(x2!=FIFO[0][Start] || y2!=FIFO[1][Start] )
{
/* запоминаем очередные координаты клетки, то есть первый
элемент в очереди
*/
x=FIFO[0][Start] ; y=FIFO[1][Start] ;
/* Необходимо проверить все ячейки, смежные с выбранной ранее.
Если некоторая из них не помечена, то ее координаты заносятся в очередь, следовательно, указатель Last увеличивается на 1.
*/
//проверяем смежную клетку справа по горизонтали
if(labirint[x+1][y] = = 0&& x+1<N)
{ FIFO[0][Last]=x+1; FIFO[1][Last]=y;
/* заносим в очередь координаты клетки, из которой попали в текущую, так как по условию задачи необходимо найти путь, то
запоминаем
координаты клетки, из которой попали в текущую
*/
FIFO[2][Last]=Start; Last++; //
labirint [x+1][y] = -1; // помечаем клетку как пройденную
}
//проверяем смежную клетку слева по горизонтали
if(labirint[x-1][y] = = 0&& x-1>=0)
{ FIFO[0][Last]=x-1; FIFO[1][Last]=y;
/* заносим в очередь координаты клетки, из
которой попали в текущую */
FIFO[2][Last]=Start;
Last++; //
labirint [x-1][y] = -1;
// помечаем клетку как пройденную
}
//проверяем смежную клетку снизу по вертикали
if(labirint[x][y+1] = = 0&& y+1<M)
{ FIFO[0][Last]=x; FIFO[1][Last]=y+1;
/* заносим в очередь координаты клетки, из которой попали в Текущую */
FIFO[2][Last]=Start; Last++; //
labirint [x][y+1] = -1; // помечаем клетку как пройденную
}
//проверяем смежную клетку сверху по вертикали
if(labirint[x][y-1] = = 0&& y-1>=0)
{ FIFO[0][Last]=x; FIFO[1][Last]=y-1;
/* заносим в очередь координаты клетки, из которой попали в текущую
*/
FIFO[2][Last]=Start; Last++; //
labirint [x][y-1] = -1; // помечаем клетку как пройденную
}
Start++; // удаляем элемент из очереди
} // конец цикла while
/* Для вывода пути будем использовать массив координат result предшествующих клеток В последнюю очередь будут выведены координаты конечной
клетки. Перед ним - координаты предыдущей клетки и тд. . */
p=Start;
/*Порядковый номер в очереди конечного элемента с координатами x2,y2*/
i=0; while(p!=0){
result[0][i]=FIFO[0][p]; result[1][i]=FIFO[1][p];
p=FIFO[2][p]; // переходим к предшествующему элементу i++;
}
// Последним элементом массива будет стартовая клетка
result[0][i]=x1; result[1][i]=y1;
//печать массива result с конца, чтобы получить путь в
//прямом порядке
for(j=I;j>=0;j--)
cout<<result[0][j]<< “ ”<< result[0][j]<<endl;
getch();
} // конец функции main
ЗАДАНИЕ*
1.Даны координаты двух клеток шахматного поля размером 8х8. Необходимо определить и вывести на экран минимальное количество
ходов, за которое конь переместиться из одной клетки в другую.
2.Напишите программу, которая определит, правильно ли расставлены
скобки (, ) в выражении. Например, (222- (2*X+5))-3*y)
3.Напишите программу, которая определит значение арифметического выражения. Например, (2+5)*8-4.
Арифметическое выражение должно вводиться с клавиатуры в одну строку без пробела.