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

Chess problem...TLE on test #10!! how to make it faster?????
Posted by michel mizrahi 12 May 2005 10:25
I really stuck with this, I don't know how to make my algorithm faster

here is my code:
#include <stdio.h>
char board[10][10];
char letter[66],num[66];
int n,s=0,ncuad;
int pos_f[8]={-1,-2,-2,-1, 1, 2, 2, 1};
int pos_c[8]={-2, 1,-1, 2, 2, 1,-1,-2};

init_board(){
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            board[i][j]='0';
}

search(int i,int f,int c){
    int j=0;
    if(s==1)
        return 0;
  if(board[f][c]=='0'){
     board[f][c]='1';
     switch(f){
           case 1: letter[i]='a';break;
        case 2: letter[i]='b';break;
        case 3: letter[i]='c';break;
        case 4: letter[i]='d';break;
               case 5: letter[i]='e';break;
               case 6: letter[i]='f';break;
               case 7: letter[i]='g';break;
               case 8: letter[i]='h';break;
     }
     num[i]=c;
     if(i==ncuad)
              s=1;
       while(j<8 && s==0){
           if((f+pos_f[j])>0 && (f+pos_f[j])<=n)
         if((c+pos_c[j])>0 && (c+pos_c[j])<=n)
               search(i+1,f+pos_f[j],c+pos_c[j]);
       j++;
     }
         board[f][c]='0';
   }
}

int main(){
    int i,j;
  scanf("%d",&n);
  ncuad=n*n;
  init_board();
     for(i=1;i<=n;i++)
         for(j=1;j<=n;j++)
           search(1,i,j);
    if(s){
       for(i=1;i<=ncuad;i++)
         printf("%c%d ",letter[i],num[i]);
         return 0;
    }
    else
     printf("IMPOSSIBLE\n");
  return 0;
}

if someone can help me I would appreciate a lot!!
Precalc (-)
Posted by Dmitry 'Diman_YES' Kovalioff 12 May 2005 12:22
see+++++++++++++
Posted by famas 12 May 2005 22:32
else
   begin
   writeln('a1');
   writeln('b3');
   writeln('a5');
   writeln('b7');
   writeln('d8');
   writeln('c6');
   writeln('b4');
   writeln('a2');
   writeln('c3');
   writeln('b1');
   writeln('a3');
   writeln('b5');
   writeln('a7');
   writeln('c8');
   writeln('b6');
   writeln('a4');
   writeln('c5');
   writeln('a6');
   writeln('b8');
   writeln('d7');
   writeln('f8');
   writeln('e6');
   writeln('d4');
   writeln('c2');
   writeln('e3');
   writeln('d1');
   writeln('b2');
   writeln('c4');
   writeln('d6');
   writeln('e8');
   writeln('g7');
   writeln('f5');
   writeln('e7');
   writeln('g8');
   writeln('f6');
   writeln('h7');
   writeln('g5');
   writeln('e4');
   writeln('d2');
   writeln('f1');
   writeln('h2');
   writeln('f3');
   writeln('e1');
   writeln('g2');
   writeln('h4');
   writeln('g6');
   writeln('h8');
   writeln('f7');
   writeln('h6');
   writeln('g4');
   writeln('e5');
   writeln('d3');
   writeln('c1');
   writeln('e2');
   writeln('g1');
   writeln('h3');
   writeln('f2');
   writeln('h1');
   writeln('g3');
   writeln('h5');
   writeln('f4');
   writeln('d5');
   writeln('c7');
   writeln('a8');
   end;
Re: see+++++++++++++
Posted by michel mizrahi 13 May 2005 07:38
thanks!
but can I ask you two questions...?
first, how many time takes in your computer if you run my code to get the solution for n=8? because my computer is veryy slow and get stuck
and number two
is it any way to solve it the problem without precalc?? (sorry for my bad english)
and thanks again!!! :D:D:D:D:)
byee! and good luck!
Re: see+++++++++++++
Posted by Burunduk1 13 May 2005 10:29
I didn't use precalc.
I calculated answer for N using answer for N-1
if it was not 'No Solution' I took first N moves from it.
I did not known C++
Posted by famas 13 May 2005 17:14
Re: Chess problem...TLE on test #10!! how to make it faster?????
Use the priority array for the chessboard :

void init()
{
    int a,b,c;
int chessboard[8][8]={0};
int direction[8][2]=
{
    {2,1},{-2,1},{2,-1},{-2,-1},
    {1,2},{-1,2},{1,-2},{-1,-2},
};
    for(a=0;a<n;a++)
    {
        for(b=0;b<n;b++)
        {
            int count=0;
            for(c=0;c<n;c++)
            {
                int x1 = a+direction[c][0];
                int y1 = b+direction[c][1];
                if(x1>=0&&x1<n&&y1>=0&&y1<n) count++;
            }
            chessboard[a][b] = count;
        }
    }
}

For example, n = 8 :

2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

go to the cell with minimum priority first !
Good luck !

Edited by author 17.02.2009 12:04

Edited by author 17.02.2009 12:04
Re: TLE on test #10!!
Posted by partisan 11 Jun 2009 02:44
How can here be >=10 tests if 1<=n<=8?
Re: Chess problem...TLE on test #10!! how to make it faster?????
Posted by frobozzz 13 Jan 2018 01:57
Great tip, thank you!