Comments (5)
CSES-Solutions/src/1689 - Knight's Tour.cpp
Lines 51 to 58 in becd3cc
empty neighbors to (x1,y1) are (x2,y2) , so why are you checking if (x1,y1) is empty on line 55
?
I just mean to say
if (x2>=1 && x2<=8 && y2>=1 && y2<=8 && !grid[**x1**][**y1**]) s++;
Should this be changed to
if (x2>=1 && x2<=8 && y2>=1 && y2<=8 && !grid[**x2**][**y2**]) s++;
from cses-solutions.
Should this be changed to
if (x2>=1 && x2<=8 && y2>=1 && y2<=8 && !grid[**x2**][**y2**]) s++;
I realized the mistake. Yes, it should be changed.
from cses-solutions.
Hello @mrsac7 can you please explain to me why do we need to sort the points,
Hello @anishagg17! Sure. I'm using Warnsdorf ’s rule. According to Antti Laaksonen - Competitive Programmer's Handbook:
Warnsdorf’s rule is a simple and effective heuristic for finding a knight’s tour. Using the rule, it is possible to efficiently construct a tour even on a large board. The idea is to always move the knight so that it ends up in a square where the number of possible moves is as small as possible.
deg
function calculates the number of moves possible from a cell. Here, I'm storing the number of moves possible from a cell (x1, y1)
in the vector vc<tiii> v
.
CSES-Solutions/src/1689 - Knight's Tour.cpp
Lines 66 to 67 in becd3cc
And then I'm sorting the cells according to the number of possible moves so that I can move my knight to the cell from which the least number of moves are possible (Warnsdorf's rule).
The grid contains 0 on empty cells and a positive number on the occupied cells. I'm checking !grid[x1][y1]
to ensure that the cell is empty. This is required because we can only move the knight on empty cells in every subsequent move.
from cses-solutions.
I'm checking !grid[x1][y1] to ensure that the cell is empty
but the cell should be grid[x2][y2], I think
from cses-solutions.
but the cell should be grid[x2][y2], I think
Suppose my knight is currently at the cell (x, y)
. From here, I will explore all the empty cells (x1, y1)
which can be reached from (x, y)
in a single move. So I need to check the empty condition for the cell (x1, y1)
.
Cells (x2, y2)
are different. They come into play when I calculate the degree of each cell (x1, y1)
. Because to calculate the degree, I need to count the number of empty cells (x2, y2)
which can be reached from (x1, y1)
. This calculation takes place in the deg
function.
from cses-solutions.
Related Issues (5)
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from cses-solutions.