fork download
copy 
  1. //Graph BFS:Codechef DIGJUMP
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define showoff    ios_base::sync_with_stdio(false)
  5. #define ll long long int
  6. #define sd(x) scanf("%d", &x)
  7. #define pf(x) printf("%d",&x)
  8. typedef vector< int > vi;
  9. typedef vector< vi > vvi;
  10. typedef pair< int,int > ii;
  11. #define sz(a) int((a).size())
  12. #define pb push_back
  13. #define all(c) (c).begin(),(c).end()
  14. #define rall(c) c.rbegin(), c.rend()
  15. #define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++)
  16. #define present(c,x) ((c).find(x) != (c).end())
  17. #define cpresent(c,x) (find(all(c),x) != (c).end())
  18. #define maxn  100001
  19. vector<int>adj[maxn];
  20. //int dist[maxn];
  21. bool visit[maxn];
  22. string s;int n;
  23. void make_graph(string s,int n){
  24.     for(int i=0;i<n;i++){
  25.         if(i==0)
  26.         adj[i].pb(i+1);
  27.         else if(i==n-1)
  28.         adj[i].pb(i-1);
  29.         else
  30.         {
  31.             adj[i].pb(i-1);
  32.             adj[i].pb(i+1);
  33.         }
  34.     for(int j=0;j<s.length();j++){
  35.         if(s[j]==s[i] && j!=i-1 && j!=i+1 && i!=j)
  36.         adj[i].pb(j);
  37.     }
  38.  
  39. }}
  40. int bfs(){
  41. 	int moves=0;
  42. 	priority_queue<int>q;
  43. 	q.push(0);
  44. 	while(!q.empty()){
  45. 		int node = q.top();
  46. 		if(node==n-1)
  47. 		break;
  48. 		if(visit[node])
  49. 		continue;
  50. 		else{
  51. 		visit[node]=true;
  52. 		moves++;
  53. 		}
  54. 		for(auto it =adj[node].begin();it!=adj[node].end();it++){
  55. 			q.push(*it);
  56. 		}
  57. 	}
  58. 	return moves;
  59. }
  60.  
  61. int main(){
  62.     for(int i=0;i<maxn;i++)
  63.     visit[i]=false;
  64.     cin>>s;
  65.     n=s.length();
  66.     make_graph(s,n);
  67.     int moves=bfs();
  68.     cout<<moves;
  69. }
Success #stdin #stdout 0s 17680KB
comments (?)
stdin
copy 
012134444444443
stdout
copy 
4
https://ideone.com/E8wgor
language:
C++14 (clang 8.0)
created:
4 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!