Algoritmo: O imperador Lu Zhin Du « Sippert, Tiago A. S.

Algoritmo: O imperador Lu Zhin Du

Posted by sippert | Filed under algoritmos

Algoritmo de Maratona de Programação utilizando recursão:

#include<iostream>
using namespace std;
int m,n,k,mat[100][100],vis[100][100];
bool recursao(int i, int j){
	if(j==n-1) return true;
	vis[i][j]=1;
	bool parcial=false;
	if((j<n-1)&&(!vis[i][j+1])&&(abs(mat[i][j+1]-mat[i][j])==k)) parcial=recursao(i,j+1);
	if((!parcial)&&(i>0)&&(!vis[i-1][j])&&(abs(mat[i-1][j]-mat[i][j])==k)) parcial=recursao(i-1,j);
	if((!parcial)&&(j>0)&&(!vis[i][j-1])&&(abs(mat[i][j-1]-mat[i][j])==k)) parcial=recursao(i,j-1);
	if((!parcial)&&(i<m-1)&&(!vis[i+1][j])&&(abs(mat[i+1][j]-mat[i][j])==k)) parcial=recursao(i+1,j);
	return parcial;
}
int main(){
	int t=1;
	while((cin >> m >> n >> k)&&(m!=0)&&(n!=0)){
		memset(vis,0,sizeof(vis));
		for(int i=0;i<m;i++)
			for(int j=0;j<n;j++)
				cin >> mat[i][j];
		bool resposta=false;
		for(int i=0;((i<m)&&(!resposta));i++) resposta=recursao(i,0);
		cout << "Instancia " << t++ << endl << ((resposta)?"sim":"nao") << endl << endl;
	}
	return 0;
}

Compartilhe: