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