PASSEIO DO CAVALO DESGOVERNADO
No jogo de Xadrez o cavalo é uma peça que descreve um movimento peculiar que tem o formato de um “L”.
Imagine um tabuleiro de xadrez com apenas um cavalo posicionado em uma casa qualquer. Imagine ainda que esse cavalo deve visitar quantas casas for possível (obviamente respeitando sua regra de movimentação), sem repetir nenhuma casa, até que visite todas as casas ou fique preso em alguma casa.
Observe o exemplo a seguir.
Nele nota-se que o cavalo saiu da posição 1, em seguida visitou a posição 2 e assim sucessivamente até chegar à posição 23, de onde o cavalo não consegue mais visitar outras casas.
Seu algoritmo deve cumprir com os seguintes requisitos mínimos:
o usuário deve poder indicar a posição de partida (casa inicial) do cavalo;
a partir da casa inicial o cavalo deve sempre escolher aleatoriamente a próxima casa a ser visitada;
cada casa visitada deve ser marcada com algum caractere para diferenciá-la de uma casa ainda não visitada;
a cada movimentação do cavalo a configuração do tabuleiro deve ser exibida ao usuário;
ao término do passeio deve ser exibido o número de casas visitadas e o número de casas não visitadas
Vamos estudar um algoritmo de grafos (DFS).
Nesse exercício vamos usar a linguagem C++:
#include<stdio.h>
#include<time.h>
char tab[8][8];
int x,y;
int nv=0;
bool in(int x,int y)
{
return x>=0 and x<8 and y>=0 and y<8;
}
void dfs()
{
tab[x][y]=’X’;
if(!(in(x+2,y-1) or tab[x+2][y-1]!=’X’) and !(in(x+2,y+1) or tab[x+2][y+1]!=’X’)
and !(in(x-2,y-1) or tab[x-2][y-1]!=’X’) and !(in(x-2,y+1) or tab[x-2][y+1]!=’X’)
and !(in(x+1,y-2) or tab[x+1][y-2]!=’X’) and !(in(x+1,y+2) or tab[x+1][y+2]!=’X’)
and !(in(x-1,y-2) or tab[x-1][y-2]!=’X’) and !(in(x-1,y+2) or tab[x-1][y+2]!=’X’))
return;
while(true)
{
int d = rand()%8;
if(d==0 and in(x+2,y-1) and tab[x+2][y-1]!=’X’)
{
x += 2; y -= 1;
return dfs();
}
if(d==0 and in(x+2,y+1) and tab[x+2][y+1]!=’X’)
{
x += 2; y += 1;
return dfs();
}
if(d==0 and in(x-2,y-1) and tab[x-2][y-1]!=’X’)
{
x -= 2; y -= 1;
return dfs();
}
if(d==0 and in(x-2,y+1) and tab[x-2][y+1]!=’X’)
{
x -= 2; y += 1;
return dfs();
}
}
}
int main()
{
printf(“Insira a casa início no formato x,y: ”);
scanf(“ %d %d”,&x,&y);
srand(time(NULL));
dfs();
printf(“Numero visitadas: %d\n”,nv);
printf(“Numero nao visitadas: %d\n”,64-nv);
return 0;
}
Para escrever sua resposta aqui, entre ou crie uma conta
Algoritmo e Programação
•UFPI
Compartilhar