Tuesday, August 27, 2013

UVA 11198 Dancing Digits

Problem Link
Problem Type : BFS.
Difficulty Level : 5
Run Time : 0.219
Author : Imdad

Briefly problem statement
Its a BFS problem. A special datastructure is used to save the visited states.
Here, is the c++ implementation of this problem.
 
#include <cstdio>
#include <map>
#include <string>
#include <queue>
#include <set>
#include <cstdlib>
#include <iostream>

using namespace std;

#define ll long long /*__int64 */

setmp;
int p[] = {0,0,2,3,0,5,0,7,0,0,0,11,0,13,0,0,0,17,0,19};
int sorted[] = {1,2,3,4,5,6,7,8};

typedef struct{
 int a[8];
 int step;
}data;

int is_prime(int n){
 return p[n];
}

bool is_sorted(int a[]){
 for(int i = 0; i < 8; i++){
  if(abs(a[i]) != sorted[i])
   return false;
 }
 return true;
}

void make_visited(int a[]){
 ll val = 0; 
 
 for(int i = 0; i < 8; i++){
  val *= 10;
  val += abs(a[i]);   
 }

 mp.insert(val);
}

int is_visited(int a[]){
 ll val = 0; 
 
 for(int i = 0; i < 8; i++){
  val *= 10;
  val += abs(a[i]);   
 }

 return mp.find(val) != mp.end();
}

void generate_step(int i, int j, int a[], bool before){
 int tmp;
 if(before){
  if(i > j){
   tmp = a[i];
   while(i > j){
    a[i] = a[i-1];
    i--;
   }
   a[i] = tmp;

  }else{
   tmp = a[i];
   while(i < j-1){
    a[i] = a[i+1];
    i++;
   }
   a[i] = tmp;
  }
 }else{
  if(i > j){
   tmp = a[i];
   while(i > j+1){
    a[i] = a[i-1];
    i--;
   }
   a[i] = tmp;

  }else{
   tmp = a[i];
   while(i < j){
    a[i] = a[i+1];
    i++;
   }
   a[i] = tmp;
  }
 }
}

void print(int a[]){
 for(int i = 0; i < 8; i++)
  printf("%d",a[i]);
 printf("\n");
}

int main(){
 int i,j,cas = 1;

 data temp,current;

 //freopen("i.txt", "r", stdin);

 while(scanf("%d", &temp.a[0]) && temp.a[0]){
  for(i = 1; i < 8; i++)
   scanf("%d", &temp.a[i]);

  mp.clear();
  make_visited(temp.a);
  temp.step = 0;
  
  queueq;
  q.push(temp);
  while(1){
   if(q.empty()){
    printf("Case %d: %d\n", cas++, -1);
    break;
   }

   current = q.front();
   q.pop();

   if(is_sorted(current.a)){
    printf("Case %d: %d\n", cas++, current.step);
    break;
   }   
   
   for(i = 0; i < 8; i++){
    if(current.a[i] < 0){
     for(j = 0; j < 8; j++){
      if(current.a[j] > 0 && is_prime(abs(current.a[i]) + current.a[j])){       

       if(abs(current.a[i]) < abs(current.a[j])){
        temp = current;
        generate_step(i,j,temp.a, true);
        if(!is_visited(temp.a)){
         make_visited(temp.a);
         temp.step++;
         q.push(temp);
        }
       }

       if(abs(current.a[j]) < abs(current.a[i])){
        temp = current;
        generate_step(j,i,temp.a, true);
        if(!is_visited(temp.a)){
         make_visited(temp.a);
         temp.step++;
         q.push(temp);
        }
       }

       if(abs(current.a[i]) > abs(current.a[j])){
        temp = current;
        generate_step(i,j,temp.a, false);
        if(!is_visited(temp.a)){
         make_visited(temp.a);
         temp.step++;
         q.push(temp);
        }
       }

       if(abs(current.a[j]) > abs(current.a[i])){
        temp = current;
        generate_step(j,i,temp.a, false);
        if(!is_visited(temp.a)){
         make_visited(temp.a);
         temp.step++;
         q.push(temp);
        }
       }
      }
     }
    }
   }


    
  }
 }

 return 0;
}

No comments:

Post a Comment