1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
|
#include <cstdlib> #include <algorithm> #include <cstring> #include <cctype> #define INF 2000000000 using namespace std; typedef long long ll; int (){ int f=1,x=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return f*x; } int n,m,pos1[1005][2],pos2[1005][2],f[1005][1005]; char s1[1005],s2[1005]; void movement(char c,int &x,int &y){ if(c=='N')y++;if(c=='S')y--; if(c=='E')x++;if(c=='W')x--; } int sqr(int a,int b){ return (pos1[a][0]-pos2[b][0])*(pos1[a][0]-pos2[b][0])+ (pos1[a][1]-pos2[b][1])*(pos1[a][1]-pos2[b][1]); } void init(){ n=read(),m=read(); pos1[0][0]=read(),pos1[0][1]=read(); pos2[0][0]=read(),pos2[0][1]=read(); scanf("%s%s",s1+1,s2+1); for(int i=1,x=pos1[0][0],y=pos1[0][1];i<=n;i++) movement(s1[i],x,y), pos1[i][0]=x,pos1[i][1]=y; for(int i=1,x=pos2[0][0],y=pos2[0][1];i<=m;i++) movement(s2[i],x,y), pos2[i][0]=x,pos2[i][1]=y; } void solve(){ memset(f,0x14,sizeof(f)); f[0][0]=0; for(int i=1;i<=n;i++) f[i][0]=f[i-1][0]+sqr(i,0); for(int i=1;i<=m;i++) f[0][i]=f[0][i-1]+sqr(0,i); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f[i][j]=min(f[i-1][j],f[i][j-1]), f[i][j]=min(f[i][j],f[i-1][j-1]), f[i][j]+=sqr(i,j); printf("%dn",f[n][m]); } int main(){ init(); solve(); return 0; }
|
近期评论