fork(2) download
copy 
  1. /* Problem: DIGJUMP
  2.    Algorithm used: String searching and BFS by implementing a graph datatype 
  3.    Time Taken : O(n^2) 
  4.    Author: brobear1995
  5.    */
  6. #include<iostream>
  7. #include <list>
  8. #include<algorithm>
  9. using namespace std;
  10.  int len;
  11. // This class represents a directed graph using adjacency list representation
  12. class Graph
  13. {
  14.     int V;    // No. of vertices
  15.     list<int> *adj;    // Pointer to an array containing adjacency lists
  16.     // void DFSUtil( int v, bool visited[]);
  17. public:
  18. int *distTo; // shortest path
  19.     Graph(int V);  // Constructor
  20.     void addEdge(int v, int w); // function to add an edge to graph
  21.     void BFS(int s);  // prints BFS traversal from a given source s
  22.    // void DFS(int v);
  23. };
  24.  
  25. Graph::Graph(int V)
  26. {
  27.     this->V = V;
  28.     adj = new list<int>[V];
  29.     distTo= new int[V];
  30.     for(int i=0;i<V;i++)
  31.     {
  32.         distTo[i]=999999;        // MAX_INT BETWEEN THE LIST
  33.     }
  34. }
  35.  
  36. void Graph::addEdge(int v, int w)
  37. {
  38.     adj[v].push_back(w); // Add w to v�¢ï¿½ï¿½s list.
  39.     adj[w].push_back(v); // undirected graph
  40.     //cout<<v<<" connected to "<<w<<"\n";
  41. }
  42.  
  43. void Graph::BFS(int s)
  44. {
  45.     // Mark all the vertices as not visited
  46.     bool *visited = new bool[V];
  47.     for(int i = 0; i < V; i++)
  48.         visited[i] = false;
  49.  
  50.      distTo[s]=0;
  51.     // Create a queue for BFS
  52.     list<int> queue;
  53.  
  54.     // Mark the current node as visited and enqueue it
  55.     visited[s] = true;
  56.     queue.push_back(s);
  57.  
  58.     // 'i' will be used to get all adjacent vertices of a vertex
  59.     list<int>::iterator i;
  60.  
  61.     while(!queue.empty())
  62.     {
  63.         // Dequeue a vertex from queue and print it
  64.         s = queue.front();
  65.               queue.pop_front();
  66.  
  67.         // Get all adjacent vertices of the dequeued vertex s
  68.         // If a adjacent has not been visited, then mark it visited
  69.         // and enqueue it
  70.         for(i = adj[s].begin(); i != adj[s].end(); ++i)
  71.         {
  72.             if(!visited[*i])
  73.             {
  74.                 visited[*i] = true;
  75.                 distTo[*i]=distTo[s]+1;
  76.                if(*i!=s)
  77.                {           
  78.                                queue.push_back(*i);          //optimised bfs
  79.                }
  80.             }
  81.         }
  82.     }
  83. }
  84.  
  85.  void solvedigjump()
  86.  {
  87.       // Create a graph given in the above diagram
  88.     string s;
  89.         cin>>s;
  90.         int k=0;
  91.     int i=0;
  92.     int j=0;
  93.  
  94.      len=s.length();
  95.     if(len==1)
  96.     {
  97.         cout<<0;
  98.         return;
  99.     }
  100.  
  101.     len--;
  102.      // create an instance for the graph class
  103.     //size_t dist =0;
  104.     /* connect adjacent elements and connect elements having smae value here */
  105.     //size_t u = s.find_first_of(s[len]);
  106.  
  107.     Graph g(len+1);
  108.     for(i=0;i<=(len-1);i++)
  109.     {
  110.         j=i;
  111.         g.addEdge(i,i+1); // connecting adjacent elements
  112.             while(j<=len)
  113.             {
  114.                // cout<<j<<"\n";
  115.                 if(s[j]==s[i])
  116.                 {
  117.                     g.addEdge(i,j);                    // connecting element having same value                   // break;
  118.                 }
  119.                 j++;
  120.             }
  121.  
  122.     }
  123.  /* Network generates in O(n^2) time */
  124.     g.BFS(0);                      // Implement Breadth First search in the network O(n) time
  125.     cout<<g.distTo[len];            // output the shortest distance
  126.  
  127.  }
  128. // Driver program to test methods of graph class
  129. int main()
  130. {
  131.    solvedigjump();
  132.     return 0;
  133. }
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
23847593857839459879879875938475938479879874593845797987948579386657657687676546546578768765465443492847987987987985765768798798237768678768908098868786764345788876567876568888888888858765
stdout
copy 
5
https://ideone.com/ie6xy9
June Challenge DIGJUMP
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!