Monday, 27 August 2018

new trying

#include<iostream>

using namespace std;
int arr[10][10];
int visited[10][10];
int min_cost;
int n;

bool isSafe(int x,int y){
 if(x>=0 && y>=0 && x<n && y<n && arr[x][y]!=0 ){return true;}
 else{return false;}
}

bool AllVisited(){
  for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(visited[i][j]!=1){return false;}
        }
    }
    return true;
}

void dfs(int x,int y,int cost){
    if(x==n-1 && y==n-1){
    if(cost<min_cost){min_cost=cost;}
    std::cout<<"one loop got completed ------- giving cost :"<<cost<<" min cost :"<<min_cost<<std::endl;
    bool k = AllVisited();
    if(k==true){std::cout<<"found the elemeents !! yay "<<std::endl;  return;}
    //if(k==false){return;}
    }

    if(isSafe(x,y)==true){
          if(arr[x+1][y]!=0 && visited[x+1][y]==0){visited[x+1][y]=1; cost=cost+arr[x+1][y]; std::cout<<"sending xy:"<<x+1<<" "<<y<<" cost :"<<cost<<std::endl; dfs(x+1,y,cost); cost=cost-(arr[x+1][y]); visited[x+1][y]=0; std::cout<<"backtracking xy:"<<x+1<<y<<" cost :"<<cost<<std::endl;}
          if(arr[x][y+1]!=0 && visited[x][y+1]==0){visited[x][y+1]=1; cost=cost+arr[x][y+1]; std::cout<<"sending xy:"<<x<<" "<<y+1<<" cost :"<<cost<<std::endl; dfs(x,y+1,cost); cost=cost-(arr[x][y+1]); visited[x][y+1]=0; std::cout<<"backtracking xy:"<<x<<y+1<<" cost :"<<cost<<std::endl;}
          if(arr[x-1][y]!=0 && visited[x-1][y]==0){visited[x-1][y]=1; cost=cost+arr[x-1][y]; std::cout<<"sending xy:"<<x-1<<" "<<y<<" cost :"<<cost<<std::endl; dfs(x-1,y,cost); cost=cost-(arr[x-1][y]); visited[x-1][y]=0; std::cout<<"backtracking xy:"<<x-1<<y<<" cost :"<<cost<<std::endl;}
          if(arr[x][y-1]!=0 && visited[x][y-1]==0){visited[x][y-1]=1; cost=cost+arr[x][y-1]; std::cout<<"sending xy:"<<x<<" "<<y-1<<" cost :"<<cost<<std::endl; dfs(x,y-1,cost); cost=cost-(arr[x][y-1]); visited[x][y-1]=0; std::cout<<"backtracking xy:"<<x<<y-1<<" cost :"<<cost<<std::endl;}

    }
return ;
}


int main(){
int t;
std::cin>>t;

for(int tc=0;tc<t;tc++){
    std::cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            std::cin>>arr[i][j];
            visited[i][j]=0;
        }
    }
      min_cost=999;
      for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
                if(arr[i][j]!=0 && visited[i][j]==0){
                    visited[i][j]=1;
                    dfs(0,0,);
                }

        }
    }


    std::cout<<"min_cost"<<min_cost<<std::endl;
}

return 0;}

No comments:

Post a Comment