Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

haha

Posted by icfire at 2017-07-03 10:38:41 on Problem 1178
#include<iostream>
#include<cstring>
#include<cmath>
#define MN 64
#define MV 100000
#define min(a,b) a<=b?a:b
#define max(a,b) a>=b?a:b
using namespace std;
int dir[8][2]={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,-2},{2,-1},{2,1},{1,2}};
int f[2][MN+1][MN+1],kn[MN+1][2],n=0,t[MN+1];
bool lim(int x, int y)
{
    return x>=0 && x<8 && y>=0 && y<8;
}
void csh()
{
    int i,j,k,t1,t2,p1,p2;
    for (i=0;i<MN;i++) for (j=0;j<MN;j++)
    {
        if (i==j) f[0][i][j]=f[1][i][j]=0;
        else f[0][i][j]=f[1][i][j]=MV;
    }
    for (i=0;i<8;i++) for (j=0;j<8;j++) for (k=0;k<8;k++)
    {
        t1=i+dir[k][0];t2=j+dir[k][1];
        if (lim(t1,t2))
        {
            p1=i*8+j;p2=t1*8+t2;
            f[0][p1][p2]=f[1][p1][p2]=1;
        }
    }
}
void floyd()
{
    int i,j,k;
    for (k=0;k<MN;k++) for (i=0;i<MN;i++) for (j=0;j<MN;j++)
    {
        f[0][i][j]=min(f[0][i][k]+f[0][k][j],f[0][i][j]);
        f[1][i][j]=min(f[1][i][k]+f[1][k][j],f[1][i][j]);
    }
}
int main()
{
    int i,j,k,D,d1,d2,x,y,ans,king,s;
    char C[150];csh();floyd();
    while (scanf("%s",C)!=EOF)
    {
        n=(strlen(C)-2)/2;ans=MV;
        if (n==0) {cout<<0;continue;}
        king=(C[0]-'A')+(C[1]-'1')*8;
        for (i=0,j=2;i<n;i++,j+=2) t[i]=(C[j]-'A')+(C[j+1]-'1')*8;
        for (i=0;i<MN;i++)
        {
            s=0;
            for (k=0;k<n;k++) s+=f[0][t[k]][i];
            for (j=0;j<MN;j++)
            {
                d1=f[1][king][j];d2=MV;
                for (k=0;k<n;k++) d2=min(d2,f[0][t[k]][j]+f[0][j][i]-f[0][t[k]][i]);
                ans=min(ans,s+d1+d2);
            }
        }
        cout<<ans<<endl;
    }
    //system("pause");
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator