Passeio do Cavalo Desgovernado [ AJUDA ]

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

Algoritmos

•

UEZO

1

0

1

0

6

Talles Magioli

06.10.2017

💡 6 Respostas

Andre Smaira

08.10.2018

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;

}

1

0

MANCHA CHANNEL

07.10.2017

Vish?

0

Joao Andre MArtins Dias

07.10.2017

Cara esse ai é osso, mas para te ajudar preciso saber se você tm que resolver de maneira Recursiva(por chamadas recusivas) ou iterativa(Com auxilio de uma estrutura do tipo PILHA para simular a recursão? Na minha facul só aceita Iterativo)

0