I saw this particular High School programming league problem, and the test data, for 4x4 chessboard shows that the # of ways for arranging the rooks; is 14. But I think, it is incorrect. I think it should be 18. Any suggestions ?
Jan '10
Nov '14
Please see my attachment, for the 4x4 board. The 'white' cells are where the rooks can be placed alone.
If you put a rook in the 3rd square of the first column, the 4th square of the second column, and the 2nd square of the third column, there are no possibilities for the last column. That immediately eliminates one of the 18 cases you have.
Exactly...
3x3x2x1 - 2x2x1x1
for(int i = 0; i < 3; i++)
for(int j = 0; j < 4; j++)
for(int k = 0; k < 4; k++)
for(int l = 1; l < 4; l++)
if(i != j && i != k && i != l && j != k && j != l && k != l)
printf("%d %d %d %d\n", i, j, k, l);
Kiedyś było sphere.spoj.pl, potem spoj.pl, a teraz jest spoj.com.
A te zadania jak najbardziej są na przeszukiwanie grafu. W BITMAP nawet w komentarzach jest wspomniany BFS i DFS - traktujesz każdą komórkę jako wierzchołek z 2..4 sąsiadami.
W MAWORK analogicznie, ale krawędzie są tylko tam gdzie jest kropka.
Ostatnie zadanie można wpisać do klasyfikatora zadań z "tools" i również wyskoczy BFS. 