ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1298. Knight

Help me please
Posted by Roma Labish[Lviv NU] 27 Feb 2007 00:30
I had use Warnsdorff heuristic, but I take wrang answer.. Maybe you can find my bug?

#include <iostream>
using namespace std;

struct minimum
{
    int minp;
    int i;
    int j;
    minimum():minp(9999),i(0),j(0){}
};
int d[9][9];
bool isnuje_hid(int i, int j,int n)
{
    if(i <= n && i >= 1 && j <= n && j >= 1)
    return true;
    else
    return false;
}
int reytung(int i,int j,int n)
{
    int k = 0;
    if(!d[i][j])
    {
            if(isnuje_hid(i+2,j+1,n))k++;
            if(isnuje_hid(i+1,j+2,n))k++;
            if(isnuje_hid(i+2,j-1,n))k++;
            if(isnuje_hid(i+1,j-2,n))k++;
            if(isnuje_hid(i-2,j+1,n))k++;
            if(isnuje_hid(i-2,j-1,n))k++;
            if(isnuje_hid(i-1,j+2,n))k++;
            if(isnuje_hid(i-1,j-2,n))k++;
    }
    else return -1;
    return k;
}

void zrobyty_hid(int & i, int & j,int n)
{
    minimum a;
    if(isnuje_hid(i+2,j+1,n))
        if(reytung(i+2,j+1,n) < a.minp && reytung(i+2,j+1,n) > 0)
        {
            a.minp = reytung(i+2,j+1,n);
            a.i = i + 2;
            a.j = j + 1;
        }
    if(isnuje_hid(i+1,j+2,n))
        if(reytung(i+1,j+2,n) < a.minp && reytung(i+1,j+2,n) > 0)
        {
            a.minp = reytung(i+1,j+2,n);
            a.i = i + 1;
            a.j = j + 2;
        }
    if(isnuje_hid(i+2,j-1,n))
        if(reytung(i+2,j-1,n) < a.minp && reytung(i+2,j-1,n) > 0)
        {
            a.minp = reytung(i+2,j-1,n);
            a.i = i + 2;
            a.j = j - 1;
        }
    if(isnuje_hid(i+1,j-2,n))
        if(reytung(i+1,j-2,n) < a.minp && reytung(i+1,j-2,n) > 0 )
        {
            a.minp = reytung(i+1,j-2,n);
            a.i = i + 1;
            a.j = j - 2;
        }
    if(isnuje_hid(i-2,j+1,n))
        if(reytung(i-2,j+1,n) < a.minp && reytung(i-2,j+1,n) > 0)
        {
            a.minp = reytung(i-2,j+1,n);
            a.i = i - 2;
            a.j = j + 1;
        }
    if(isnuje_hid(i-2,j-1,n))
        if(reytung(i-2,j-1,n) < a.minp && reytung(i-2,j-1,n) > 0)
        {
            a.minp = reytung(i-2,j-1,n);
            a.i = i - 2;
            a.j = j - 1;
        }
    if(isnuje_hid(i-1,j+2,n))
        if(reytung(i-1,j+2,n) < a.minp && reytung(i-1,j+2,n) > 0)
        {
            a.minp = reytung(i-1,j+2,n);
            a.i = i - 1;
            a.j = j + 2;
        }
    if(isnuje_hid(i-1,j-2,n))
        if(reytung(i-1,j-2,n) < a.minp && reytung(i-1,j-2,n) > 0)
        {
            a.minp = reytung(i-1,j-2,n);
            a.i = i - 1;
            a.j = j - 2;
        }
    if(i && j)
    {
        i = a.i;
        j = a.j;
    }
    d[i][j] = 1;
}
char convert(int n)
{
    switch(n)
    {
    case 1: return 'a';
    case 2: return 'b';
    case 3: return 'c';
    case 4: return 'd';
    case 5: return 'e';
    case 6: return 'f';
    case 7: return 'g';
    case 8: return 'h';
    }
}
int main()
{
    int n;
    cin >> n;
    if(n < 5 && n > 1){cout << "IMPOSSIBLE"; return 0;}
    int m = 1,k = 1;
    d[1][1] = 1;d[0][1] = 1;d[1][0] = 1;d[0][0] = 1;
    for(int i = 1; i <= n*n; i++)
    {
        cout << convert(m) << k << endl;
        zrobyty_hid(m,k,n);
    }
    return 0;
}

Edited by author 27.02.2007 00:32

Edited by author 27.02.2007 02:42
Re: Help me please
Posted by Astekinane 3 Oct 2011 20:33
My algorithm based on Warnsdorff rule got AC. Check your realisation.