Thursday 16 July 2015

SPOJ -> A_W_S_N - Happy Valentine Day (Valentine Maze Game)

#include<bits/stdc++.h>
using namespace std;
int ans;
void cst(int ar[12][12],int node , int dest , int size , int cost,int vis[12],int collect)
{
      if(cost > ans )
      return;
      if(node == dest)
      {
          if(collect == size)
          {
                ans = min(ans,cost);
                return;
          }

      }

     for(int i = 1 ; i <= size ; ++i )
     {
         if(vis[i] == 0 && i != node)
         {
             vis[i] = 1;
            cst(ar,i,dest,size,cost+ar[node][i],vis,collect+1);
            vis[i] = 0;
          }
     }

}
int main(){
          ios_base::sync_with_stdio(false);
            int t;
           cin >> t;
           while(t--){

              int n  , m;
              cin >> n >> m;

                string x[n+1];
                for(int i = 0 ; i < n ; ++i )
                    cin >> x[i];

                 vector<int> graph[10001];
                       int source;
                       int dest;
                       vector<int> choc;
                 for(int i = 0 ;  i < n ; ++i ){
                    for(int j = 0 ; j < m ; ++j )
                       {
                            if(x[i][j] != '#')
                            {
                       int node1 = i*m+(j+1);
                       if(x[i][j]=='C')
                         choc.push_back(node1);
                         else
                         if(x[i][j]=='T')
                          source = node1;
                          else
                          if(x[i][j] =='W')
                          dest = node1;
                                if(i+1 < n )
                                {
                                    int node2 = (i+1)*m+(j+1);
                                    graph[node1].push_back(node2);
                                    graph[node2].push_back(node1);
                                }
                                if(j+1<m)
                                {
                                 int node2 = i*m + (j+2);
                                    graph[node1].push_back(node2);
                                    graph[node2].push_back(node1);
                                }
                        }
                    }
                 }
                 int arr[12][12]={0};
                  int dist[10001];
                  int visit[10001];
                   for(int i = 0 ; i <= 10000 ; ++i ){
                      dist[i] = 1e9;
                      visit[i] = 0;
                   }
                     queue<int> q;
                     q.push(source);
                      dist[source] = 0 ;
                      while(!q.empty())
                      {
                          int u  = q.front();
                           q.pop();
                          if(visit[u] == 1)
                           continue;
                          for(int i = 0 ; i < graph[u].size() ; ++i )
                          {
                              int v = graph[u][i];
                              if(visit[v] == 0)
                              {
                                   if(dist[v] == 0)
                                  dist[v] = dist[u] + 1;
                                  else
                                  dist[v] = min(dist[v] , dist[u]+1);
                                   q.push(v);
                              }

                          }
                          visit[u] = 1;
                      }
                    for(int i = 0 ; i < choc.size() ; ++i )
                    {
                        arr[1][i+2] = dist[choc[i]];
                    }
                    arr[1][choc.size()+2] = dist[dest];
                    arr[choc.size()+2][1] = dist[dest];
                    for(int j = 0 ; j < choc.size() ; ++j )
                    {
                        for(int i = 0 ; i <= 10000 ; ++i )
                         {
                              dist[i] = 1e9;
                              visit[i] = 0;
                            }
                              q.push(choc[j]);
                      dist[choc[j]] = 0 ;
                      while(!q.empty())
                      {
                          int u  = q.front();
                           q.pop();
                          if(visit[u] == 1)
                           continue;
                          for(int i = 0 ; i < graph[u].size() ; ++i )
                          {
                              int v = graph[u][i];
                              if(visit[v] == 0)
                              {
                                  dist[v] = dist[u] + 1;
                                   q.push(v);
                              }

                          }
                          visit[u] = 1;
                      }
                      arr[j+2][1] = dist[source];
                      arr[j+2][choc.size()+2]= dist[dest];
                      arr[choc.size()+2][j+2]= dist[dest];
                     for(int i = 0 ; i < choc.size() ; ++i )
                         arr[j+2][i+2] = dist[choc[i]];
                      }
                      int size = choc.size()+2;
                      int flag = 0;
                      for(int i = 1 ; i <= size ; ++i )
                      {
                           for(int j = 1 ; j <= size ; ++j )
                               if(arr[i][j] == 1e9)
                                 flag = 1;
                      }
                          if(flag == 1)
                     cout <<"Mission Failed!"<<endl;
                     else{
                         ans = 1e9;
                         int vis[13]={0};
                           vis[1] = 1;
                        cst(arr,1,size,size ,0,vis,1);
                        cout << ans << endl;
                     }

           }
           return 0;
}

No comments:

Post a Comment