알고리즘 과제 PA5

n*n 격자에서 갈 수 있는 모든 경로 (돌아가는 길 포함) 경우의 수를 세는 알고리즘인데 수행시간이 너무 오래 걸린다.

5*5까지 가능함.

#include "grid.h"
#include <iostream>

using namespace std;
unsigned long long grid::numOfWays(void){
	int visited[10][10]={0};
	visited[0][0]=1;
	fun(visited, 0,0); 
	return result;
}

int grid::fun(int (*arr)[10], int a, int b){
	if(a==n&&b==n){
		result+=1;
		arr[a][b]=0;
		return 0;
	}
	if(arr[a+1][b]==0||arr[a-1][b]==0||arr[a][b-1]==0||arr[a][b+1]==0){//삭제 후보 3  
	}
	else{ 
		return 0;
	}

	int newvisited[10][10]={0};

	for(int i = 0; i <n+1 ; i++){ //삭제 후보 4
		for(int j =0; j<n+1 ; j++){
			newvisited[i][j] = arr[i][j];
		}
	}
	if(newvisited[a+1][b]==0&&a+1>=0&&a+1<=n){
		newvisited[a+1][b]=1;
		fun(newvisited, a+1, b);
		arr[a][b]=0;
	}

	if(newvisited[a][b+1]==0&&b+1>=0&&b+1<=n){
		newvisited[a][b+1]=1;
		fun(newvisited, a, b+1);
		arr[a][b]=0;
	}

	if(newvisited[a-1][b]==0&&a-1>=0&&a-1<=n){
		newvisited[a-1][b] =1;
		fun(newvisited, a-1, b);
		arr[a][b]=0;
	}

	if(newvisited[a][b-1]==0&&b-1>=0&&b-1<=n){
		newvisited[a][b-1]=1;
		fun(newvisited, a, b-1);
		arr[a][b]=0;
	}
	
}