Friday, 19 February 2016

UVa 439 - Knight Moves

#include<bits/stdc++.h>
using namespace std;
int graph[50][50];
int visited[50][50];
int level[50][50];
int x[8]={-2,-2,2,2,1,1,-1,-1};
int y[8]={-1,1,-1,1,-2,2,-2,2};
int main()
{
    string s1,s2;
    while(cin>>s1>>s2)
    {
        memset(graph,0,sizeof(graph));
        memset(visited,0,sizeof(visited));
        memset(level,0,sizeof(level));
        queue<int>q;
        int stx,sty,enx,eny;
        stx=s1[0]-96;
        sty=s1[1]-48;
        enx=s2[0]-96;
        eny=s2[1]-48;
        visited[stx][sty]=true;
        level[stx][sty]=0;
        q.push(stx);
        q.push(sty);
        int ans;
        while(!q.empty())
        {
            int f1,f2;
            f1=q.front();
            q.pop();
            f2=q.front();
            q.pop();
            for(int in=0;in<8;in++)
            {
                int v1,v2;
                v1=f1+x[in];
                v2=f2+y[in];
                if(!visited[v1][v2]&&!level[v1][v2])
                {
                    if(v1>=1&&v1<=8&&v2>=1&&v2<=8)
                    {
                        level[v1][v2]=level[f1][f2]+1;
                        if(v1==enx&&v2==eny)
                            ans=level[v1][v2];
                        q.push(v1);
                        q.push(v2);
                        visited[v1][v2]=true;
                    }
                }
            }
        }
        cout<<"To get from "<<s1<<" to "<<s2<<" takes ";
        if(stx==enx&&sty==eny)
            cout<<0;
        else
            cout<<ans;
        cout<<" knight moves.\n";
    }
    return 0;
}

No comments:

Post a Comment