[USACO 2016 Jan G]Radio Contact

Farmer John has lost his favorite cow bell, and Bessie the cow has agreed to help him find it! They both fan out and search the farm along different paths, but stay in contact via radio so they can keep in touch with each-other. Unfortunately, the batteries in their radios are running low, so they want to plan their movements so as to conserve power, by trying to stay always within a short distance apart.
Farmer John starts at location (fx,fy) and plans to follow a path consisting of N steps, each of which is either 'N' (north), 'E' (east), 'S' (south), or 'W' west. Bessie starts at location (bx,by) and follows a similar path consisting of M steps. Both paths may share points in common. At each time step, Farmer John can either stay put at his current location, or take one step forward along his path, in whichever direction happens to be next (assuming he has not yet reached the final location in his path). Bessie can make a similar choice. At each time step (excluding the first step where they start at their initial locations), their radios consume energy equal to the square of the distance between them.

Please help FJ and Bessie plan a joint movement strategy that will minimize the total amount of energy consumed up to and including the final step where both of them first reach the final locations on their respective paths.

The first line of input contains N and M (1≤N,M≤1000). The second line contains integers fx and fy, and the third line contains bx and by (0≤fx,fy,bx,by≤1000). The next line contains a string of length N describing FJ's path, and the final line contains a string of length M describing Bessie's path.
It is guranteed that Farmer John and Bessie's coordinates are always in the range (0≤x,y≤1000) throughout their journey. Note that East points in the positive x direction and North points in the positive y direction.

#include<bits/stdc++.h> using namespace std; const int MAX=1<<10; int dp[MAX][MAX],n,m,x,y,x2,y2; int a[MAX][2],b[MAX][2]; void Scan(int num,int x,int y,int arr[][2]){ char ch; arr[0][0]=x; arr[0][1]=y; for(int i=1;i<=num;++i){ ch=getchar(); switch(ch){ case 'N': y++; break; case 'S': y--; break; case 'W': x--; break; default: x++; } arr[i][0]=x; arr[i][1]=y; } getchar(); } int dis(int* a,int* b){ return ((a[0]-b[0])*(a[0]-b[0])+(a[1]-b[1])*(a[1]-b[1])); } void solve(){ memset(dp,0x3f,sizeof(dp)); dp[0][0]=0; for(int i=1;i<=n;i++) dp[i][0]=dp[i-1][0]+dis(a[i],b[0]); for(int j=1;j<=m;j++) dp[0][j]=dp[0][j-1]+dis(a[0],b[j]); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ dp[i][j]=min({dp[i-1][j-1],dp[i][j-1],dp[i-1][j]})+dis(a[i],b[j]); } } printf("%d\n",dp[n][m]); } int main(){ scanf("%d%d%d%d%d%d",&n,&m,&x,&y,&x2,&y2); getchar(); Scan(n,x,y,a); Scan(m,x2,y2,b); solve(); return 0; }

详情