fork download
copy 
  1. #include<stdio.h>
  2. struct xy {int x, y;}A[1212],B[1212];
  3. int D[1212][1212];
  4. int T[256];
  5. int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
  6. int dist(xy a, xy b) {return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);}
  7. int min(int a, int b) { if (a < b)return a; return b; }
  8. int main() {
  9. 	T['N'] = 0, T['S'] = 1, T['E'] = 2, T['W'] = 3;
  10. 	int n, m, i, j;
  11. 	char x;
  12. 	scanf("%d%d", &n, &m);
  13. 	scanf("%d%d", &A[0].x, &A[0].y); scanf("%d%d", &B[0].x, &B[0].y);
  14. 	for (i = 1; i <= n; i++) scanf(" %c", &x), A[i] = { A[i - 1].x + dx[T[x]],A[i - 1].y + dy[T[x]] };
  15. 	for (i = 1; i <= m; i++) scanf(" %c", &x), B[i] = { B[i - 1].x + dx[T[x]],B[i - 1].y + dy[T[x]] };
  16. 	D[0][0] = 0;
  17. 	for (i = 0; i <= n; i++) {
  18. 		for (j = 0; j <= m; j++) {
  19. 			if (i == 0 && j == 0)continue;
  20. 			D[i][j] = 2e9;
  21. 			if (i > 0)D[i][j] = min(D[i][j], D[i - 1][j]+ dist(A[i], B[j]));
  22. 			if (j > 0)D[i][j] = min(D[i][j], D[i][j - 1]+ dist(A[i], B[j]));
  23. 			if (i > 0 && j > 0)D[i][j] = min(D[i][j], D[i - 1][j - 1]+ dist(A[i], B[j]));
  24. 		}
  25. 	}
  26. 	printf("%d", D[n][m]);
  27. 	return 0;
  28. }
Success #stdin #stdout 0s 4224KB
comments (?)
stdin
copy 
2 7
3 0
5 0
NN
NWWWWWN
stdout
copy 
28
https://ideone.com/VgCObo
language:
C++14 (gcc 8.3)
created:
6 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!