fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <vector>
  4. #include <queue>
  5. using namespace std;
  6. typedef unsigned long long ULL;
  7.  
  8. int n,m;
  9. int in[8][8];
  10. int id[8][8];
  11. int color[64];
  12. int mm[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
  13. int con[64][64];
  14. ULL eg[64][6];
  15. const int H=3333331;
  16. vector<ULL> hash[H];
  17.  
  18. class State{ 
  19.     public:
  20. 	ULL s;
  21. 	ULL mask[6];
  22. 	int dis;
  23. 	State(){
  24. 	    s=1;
  25. 	    for( int i=0; i<6; i++ ){
  26. 		mask[i]=eg[0][i];
  27. 	    }
  28. 	    dis=0;
  29. 	}
  30. 	State(ULL y,const State& x){
  31. 	    s=y;
  32. 	    dis=x.dis+1;
  33. 	    y^=x.s;
  34. 	    for( int k=0; k<6; k++ ){
  35. 		mask[k]=x.mask[k];
  36. 	    }
  37. 	    for( int j=0; j<n; j++ ){
  38. 		if(y&(1ULL<<j)){
  39. 		    for( int k=0; k<6; k++ ){
  40. 			mask[k]|=eg[j][k];
  41. 		    }
  42. 		}
  43. 	    }
  44. 	}
  45. };
  46.  
  47. inline int find(ULL x){
  48.     int h=x%H;
  49.     for( int i=0; i<hash[h].size(); i++ ){
  50. 	if(hash[h][i]==x) return 0;
  51.     }
  52.     hash[h].push_back(x);
  53.     return 1;
  54. }
  55.  
  56. void flood_fill(int x,int y,int z,int d){
  57.     if(x>=0 && y>=0 && x<m && y<m && in[x][y]==z && id[x][y]==-1){
  58. 	id[x][y]=d;
  59. 	for( int i=0; i<4; i++ ){
  60. 	    flood_fill(x+mm[i][0],y+mm[i][1],z,d);
  61. 	}
  62.     }
  63. }
  64.  
  65. void create_graph(){
  66.     n=0;
  67.     memset(id,-1,sizeof(id));
  68.     memset(con,0,sizeof(con));
  69.     for( int i=0; i<m; i++ ){
  70. 	for( int j=0; j<m; j++ ){
  71. 	    if(id[i][j]==-1){
  72. 		flood_fill(i,j,in[i][j],n);
  73. 		color[n]=in[i][j];
  74. 		n++;
  75. 	    }
  76. 	}
  77.     }
  78.     for( int i=0; i<m; i++ ){
  79. 	for( int j=0; j<m; j++ ){
  80. 	    for( int k=0; k<4; k++ ){
  81. 		int dx=i+mm[k][0],dy=j+mm[k][1];
  82. 		if(dx>=0 && dy>=0 && dx<m && dy<m){
  83. 		    con[id[i][j]][id[dx][dy]]=1;
  84. 		}
  85. 	    }
  86. 	}
  87.     }
  88.     for( int i=0; i<n; i++ ){
  89. 	for( int j=0; j<6; j++ ){
  90. 	    eg[i][j]=0;
  91. 	    for( int k=0; k<n; k++ ){
  92. 		if(con[i][k] && color[k]==j){
  93. 		    eg[i][j]|=(1ULL<<k);
  94. 		}
  95. 	    }
  96. 	}
  97.     }
  98. }
  99.  
  100. int main(){
  101.     while(scanf("%d",&m) && m){
  102. 	for( int i=0; i<m; i++ ){
  103. 	    for( int j=0; j<m; j++ ){
  104. 		scanf("%d",&in[i][j]);
  105. 	    }
  106. 	}
  107. 	for( int i=0; i<H; i++ ){
  108. 	    hash[i].clear();
  109. 	}
  110. 	create_graph();
  111. 	queue<State> que;
  112. 	que.push(State());
  113. 	find(1);
  114. 	ULL target=n==64?0xffffffffffffffffULL:(1ULL<<n)-1;
  115. 	while(!que.empty()){
  116. 	    State x=que.front();
  117. 	    que.pop();
  118. 	    if(x.s==target){
  119. 		printf("%d\n",x.dis);
  120. 		break;
  121. 	    }
  122. 	    for( int i=0; i<6; i++ ){
  123. 		ULL y=x.s|x.mask[i];
  124. 		if(y!=x.s && find(y)){
  125. 		    que.push(State(y,x));
  126. 		}
  127. 	    }
  128. 	}
  129.     }
  130.     return 0;
  131. }
Success #stdin #stdout 0.06s 41768KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0ziGa6
language:
C++ (gcc 8.3)
created:
12 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!