shreyas_171's blog

KNIGHT MOVE
By shreyas_171, history, 4 years ago, In English

Can anyone just tell me Whats's wrong with my Code ??

Problem : Daniel is a chess player. At his free time, he usually plays chess with his family or his friends. But, sometimes they have their own activities, so Daniel can't play chess. He spends his time to learn about knight's move. He has 1,000 x 1,000 chessboard, numbered from 1 to 1,000. He wants to move his knight from (a,b) to (1,1) with minimum movement. Help Daniel to solve it.

KNMOVE

MY CODE : 

#include <bits/stdc++.h>
using namespace std;

#define fast                    ios_base::sync_with_stdio(false);  cin.tie(NULL);
#define time                    cerr<<"Time taken : " <<(float)clock()/CLOCKS_PER_SEC <<" secs"<<"\n"  ;
#define F                       first
#define S                       second
#define pb                      push_back
typedef long long int           ll  ;
#define INF                     1e15
#define MOD                     (int)1e9+7

// #define TRACE
// #ifdef TRACE
// #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
// template <typename Arg1>
// void __f(const char* name, Arg1&& arg1) {
//     cerr << name << " : " << arg1 << std::endl;
// }
// template <typename Arg1, typename... Args>
// void __f(const char* names, Arg1&& arg1, Args&&... args) {
//     const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
// }
// #else
// #define trace(...)
// #endif



ll  visit[1004][1004]  ;

ll  chess[1004][1004] ;


ll dx[] = {2, 2, -2, -2, 1, 1, -1, -1};
ll dy[] = { -1, 1, -1, 1, 2, -2, 2, -2};


bool VALID( ll x , ll  y) {


    return (x >= 0  && x < 1000 && y >= 0 && y < 1000)  ;

}
void BFS(ll a , ll b) {

    memset(chess , 0 , sizeof (chess))  ;
    memset(visit , 0 , sizeof(visit))  ;

    visit[a][b] = 1;

    chess[a][b] = 0;

    queue<pair<ll, ll>>q ;

    q.push({a , b}) ;

    while (!q.empty()) {


        pair<ll, ll>curr  =  q.front()  ;
        q.pop()  ;

        for (int i = 0 ; i < 8 ; i++) {

            ll  curr_x =  curr.F + dx[i];
            ll  curr_y = curr.S + dy[i];

            if (VALID(curr_x , curr_y) && !visit[curr_x][curr_y]) {

                visit[curr_x][curr_y] = 1 ;
                chess[curr_x][curr_y] = chess[curr.F][curr.S] + 1;
                q.push({curr_x , curr_y})   ;
            }
        }
    }

}



int32_t main() {

    fast ; time;
    BFS(1, 1)  ;

#ifndef ONLINE_JUDGE
    freopen("input.txt" , "r" , stdin)  ;
    freopen("output.txt" , "w" , stdout)  ;
#endif

    ll t = 1;
    cin >> t;

    while (t--) {


        ll x, y;
        cin >> x >> y;

        cout << chess[x][y] << "\n"  ;


    }


    return 0  ;
}
  • Vote: I like it
  • -19
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the problem statement, rows and columns are numbered from 1 to 1000, but in your code they're numbered from 0 to 999. So, when querying, you should subtract 1 from both x and y.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It is an indexing problem. In the lines:

BFS(1, 1)  ;

and 

cin >> x >> y;
cout << chess[x][y] << "\n"  ;

you use 1-indexed (1,2,3,.....,n) similar to what they used in the problem statement.

However, in the function Valid you check based on zero index:

return (x >= 0  && x < 1000 && y >= 0 && y < 1000)  ;

In 1-indexed notation, 1 <= x,y <= 1000, whereas in 0-indexed notation, 0 <= x,y < 1000. Thus, to correct it, you can just change the line to:

return (x >= 1  && x <= 1000 && y >= 1 && y <= 1000)  ;

Note: When using 1-indexed notation, you have to change the size of the arrays to be >= n+1 rather than >= n (which is the case in 0-indexed notation). However, as you have already initialized the array at a larger value than required, you don't have to make any changes.

→ Reply