fork download
copy 
  1.  
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. class edge{
  8. 	public:
  9.  
  10. 	int x,y,dir,c;
  11.  
  12. 	edge(int a, int b, int d){
  13. 		x=a; y=b; c=d;
  14.  
  15. 	}
  16.  
  17. 	bool operator < (const edge &other) const{
  18.  
  19. 		return c > other.c;
  20. 	}
  21. }; 
  22.  
  23. int n,m;
  24. string A;
  25.  
  26. char matrix[55][55];
  27. vector <edge> adj[55][55];
  28.  
  29. int mark[55][55];
  30. int xx,yy;
  31. int movx[]={1,-1,0,0};
  32. int movy[]={0,0,1,-1};  
  33.  
  34. void BFS (int x,int y){
  35.  
  36. 	queue <edge> cola;
  37.  
  38. 	cola.push(edge(x,y,0));
  39. 	memset(mark,-1,sizeof(mark));
  40. 	while (!cola.empty()){
  41. 		edge v = cola.front(); cola.pop();
  42.  
  43. 		if (mark[v.x][v.y]>0) continue;
  44. 		adj[x][y].push_back(edge(v.x,v.y,v.c));
  45. 		mark[v.x][v.y]=v.c;
  46. 		for (int i=0;i<4;++i){
  47. 			int aux= movx[i]+v.x;
  48. 			int auy= movy[i]+v.y;
  49.  
  50. 			if (aux<0 || auy<0 || aux>=n || auy>=m || mark[aux][auy]>=0) continue;
  51.  
  52. 			if (matrix[aux][auy]==matrix[v.x][v.y]){
  53. 				while (matrix[aux][auy]==matrix[v.x][v.y]){
  54. 					int auxx= aux+movx[i];
  55. 					int auyy= auy+movy[i];
  56.  
  57. 					if (auxx<0 || auyy<0 || auxx>=n || auyy>=m) break;
  58. 					mark[aux][auy]=0;
  59. 					aux=auxx;
  60. 					auy=auyy;
  61. 				}
  62. 			}
  63. 			if (matrix[v.x][v.y]!=matrix[aux][auy] && mark[aux][auy]<0)
  64. 			mark[aux][auy]=0;
  65. 			cola.push(edge(aux,auy,v.c+1));
  66. 		}
  67. 	}
  68.  
  69. }
  70.  
  71. int dijkstra (char B){
  72.  
  73. 	memset(mark,0x3f3f3f3f,sizeof(mark));
  74.  
  75. 	priority_queue <edge> cola; cola.push(edge(xx,yy,0));
  76.  
  77. 	while (!cola.empty()){
  78. 		edge v = cola.top(); cola.pop();
  79.  
  80. 		if (matrix[v.x][v.y]==B){
  81. 			xx=v.x; yy=v.y;
  82. 			return v.c;
  83. 		}
  84.  
  85. 		if (matrix[v.x][v.y]<v.c) continue;
  86.  
  87. 		for (int i=0;i<adj[v.x][v.y].size();++i){
  88. 			int p = adj[v.x][v.y][i].x;
  89. 			int q = adj[v.x][v.y][i].y;
  90. 			int cc= adj[v.x][v.y][i].c + v.c;
  91.  
  92. 			if (cc >= mark[p][q]) continue;
  93. 			mark[p][q]=cc;
  94. 			cola.push(edge(p,q,cc));
  95. 		}
  96. 	}
  97. }
  98.  
  99. int main(){
  100.  
  101.  
  102.         scanf("%d %d",&n,&m);
  103.  
  104.         for (int i=0;i<n;++i)
  105.                 scanf("%s",matrix[i]);
  106.  
  107.  
  108.         int cont=0;
  109.         cin>>A;
  110. 			for (int i=0;i<n;++i){
  111. 				for (int j=0;j<m;++j){
  112.  
  113. 					BFS(i,j);
  114. 				}
  115. 			}
  116.  
  117.         A.push_back('*');
  118.         cont+=A.size();
  119.  
  120.         xx=0; yy=0;
  121.         for (int i=0;i<A.size();++i){
  122. 			cont+=dijkstra(A[i]);
  123. 		}
  124.  
  125.  
  126.         printf("%d\n",cont);
  127.         return 0;
  128. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
5 20
12233445566778899000
QQWWEERRTTYYUUIIOOPP
-AASSDDFFGGHHJJKKLL*
--ZZXXCCVVBBNNMM--**
--------------------
ACM-ICPC-WORLD-FINALS-2015
stdout
copy 
147
https://ideone.com/tOGF48
language:
C++ (gcc 8.3)
created:
283 days 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!