Дана шахматная доска 8х8 клеток
В левом нижнем углу король
Он может двигаться вверх, вправо или вверх и вправо по диагонали
Слолько различных путей у короля из левого нижнего угла в правый верхний если он не совершает более 3 движений подряд в одном и том же направлении ?
Здравствуйте, adontz, Вы писали:
A>Дана шахматная доска 8х8 клеток A>В левом нижнем углу король A>Он может двигаться вверх, вправо или вверх и вправо по диагонали A>Слолько различных путей у короля из левого нижнего угла в правый верхний если он не совершает более 3 движений подряд в одном и том же направлении ?
#define restrictedLength 4
unsigned countMoves()
{
unsigned board[2*8+restrictedLength][2*8+restrictedLength];
//чтобы не заморачиваться с ходьбой по диагонали
memset(board, 0, sizeof(board));
board[7][7] = 1;
for(unsigned moveNo = 0; moveNo != 14; ++moveNo)
//идем изверхнего правого в нижний левый уголfor(unsigned x = 0, y = 13 - moveNo; x != 14 - moveNo; ++x, --y)
board[x][y] = board[x+1][y] + board[x+1][y+1] + board[x][y+1] -
board[x+restrictedLength][y] -
board[x+restrictedLength][y+restrictedLength] -
board[x][y+restrictedLength];
return board[0][0];
}
Здравствуйте, adontz, Вы писали:
A>Дана шахматная доска 8х8 клеток A>В левом нижнем углу король A>Он может двигаться вверх, вправо или вверх и вправо по диагонали A>Слолько различных путей у короля из левого нижнего угла в правый верхний если он не совершает более 3 движений подряд в одном и том же направлении ?
Напрашивается волновой алгоритм.
Фронт волны #k — это ячейки [0,k]..[k,k]..[k,0]
В каждой ячейке нужно хранить сумму "входов в нее", с учетом предыстории.
Т.е.
struct cell
{
int x[1..3], y[1..3], d[1..3]; // да простят мне этот псевдокод :)
};
x[1] означает, что в эту ячейку можно попасть N путями, причем последний ход — это одиночный шаг по x.
x[2] — соответственно, двойной шаг по x.
И так далее.
(x[0] я здесь не использую — просто для лучшей ясности кода)
Теперь определим правила подсчета.
Изначально все ячейки обнулены.
Переход от одной ячейки (уже посчитанной) к другой:
step_x(cell const& from, cell& to)
{
// если это первый шаг по x...
to.x[1] += from.y[1]+from.y[2]+from.y[3]
+ from.d[1]+from.d[2]+from.d[3];
// и если не первый...
to.x[2] = from.x[1];
to.x[3] = from.x[2];
}
и аналогично для y и d.
Чтобы правильно начать подсчет, инициализируем первый фронт (один шаг от старта):
step_first(cell& to, int x, int y, int d)
{
to.x[1] = x; to.y[1] = y; to.d[1] = d;
// только один из параметров равен 1, остальные - нули
}
После этого по каждому (в том числе и по первому) фронту производим забег:
Здравствуйте, Andy77, Вы писали:
A>Мне показалось, что задачу предлагается решать аналитически... что скажет автор?
Автор не имеет ни малейшего понятия ни о решении, ни о методах решеия. Я просто усложнил задачу ограничением в 3 хода в одном направлении. Думаю можно решить и аналитически, хотя это и сложнее чем изначальная задача.
Здравствуйте, Кодт, Вы писали:
К><>
К>Напрашивается волновой алгоритм. К>Фронт волны #k — это ячейки [0,k]..[k,k]..[k,0]
К>В каждой ячейке нужно хранить сумму "входов в нее", с учетом предыстории. К>Т.е. К>
К>struct cell
К>{
К> int x[1..3], y[1..3], d[1..3]; // да простят мне этот псевдокод :)
К>};
К>
Примерно так и решал , только на листочке
Возникает вопрос, а нужно ли хранить дополнительные данные о 9ти классах путей
в каждой ячейке или можно обойтись меньшим количеством вспомогательных данных?
Здравствуйте, kinstintin, Вы писали:
K>Возникает вопрос, а нужно ли хранить дополнительные данные о 9ти классах путей K>в каждой ячейке или можно обойтись меньшим количеством вспомогательных данных?
Здравствуйте, adontz, Вы писали:
A>Дана шахматная доска 8х8 клеток A>В левом нижнем углу король A>Он может двигаться вверх, вправо или вверх и вправо по диагонали A>Слолько различных путей у короля из левого нижнего угла в правый верхний если он не совершает более 3 движений подряд в одном и том же направлении ?
21692
Правильность работы алгоритма можно проверить на меньших досках (например 3х3) и меньших ограничениях (2)
-----------------------------------------------------------
#include <vector>
#include <queue>
#include <iostream>
struct pos
{
pos():x(0), y(0) {}
pos(int _x, int _y) : x(_x), y (_y) {}
pos(const pos& s) :x(s.x), y(s.y) {}
int x, y;
pos& operator += ( const pos& p ) { x += p.x; y += p.y; return *this;}
bool operator == ( const pos& p ) const { return (x == p.x) && (y == p.y); }
bool operator != ( const pos& p ) const { return ! operator ==(p); }
};
const pos UP(0, 1);
const pos RI(1, 0);
const pos UR(1, 1);
const pos SIZE(8, 8); // size of boardconst int ONEDIR = 3; // not allowed steps in one directiontypedef std::vector<pos> moves;
struct pathes
{
pos _start;
pos _end;
moves _moves;
std::ostream& out(std::ostream& o);
};
std::ostream&
pathes::out(std::ostream &o)
{
o << "----------------------------" << std:: endl;
for(int i = 0; i < _moves.size(); i++)
{
if(_moves[i] == UP)
o << " UP ";
else if(_moves[i] == RI)
o << " RI ";
else if(_moves[i] == UR)
o << " UR ";
else
o << " :( ";
}
o << std::endl;
return o;
}
std::queue<pathes> _pathes;
std::vector<pathes> _result;
bool check(const moves &m, const pos &p)
{
int to = m.size() - ONEDIR + 1;
if ( to >= 0 )
{
for(int i = m.size() - 1; i >= to; i--)
if(m[i] != p)
return true;
return false;
}
return true;
}
moves get_allow_moves(const pathes& path)
{
moves res;
if((path._end.x != SIZE.x) && check(path._moves, RI))
res.push_back(RI);
if((path._end.y != SIZE.y) && check(path._moves, UP))
res.push_back(UP);
if((path._end.x != SIZE.x) && (path._end.y != SIZE.y) && check(path._moves, UR))
res.push_back(UR);
return res;
}
void scan()
{
while(!_pathes.empty())
{
pathes cur = _pathes.front();
moves mov = get_allow_moves(cur);
if( cur._end == SIZE)
_result.push_back(cur);
else
for( int i = 0; i < mov.size(); i++)
{
pathes np(cur);
np._end += mov[i];
np._moves.push_back(mov[i]);
_pathes.push(np);
}
_pathes.pop();
}
}
int
main()
{
pathes first;
first._start.x = 1;
first._start.y = 1;
first._end.x = 1;
first._end.y = 1;
_pathes.push(first);
scan();
std::cout << "found " << _result.size() << " pathes";
// uncomment if want to view pathes
// for(int i = 0; i < _result.size(); i++)
// _result[i].out(std::cout);char ch;
std::cin >> ch;
return 0;
}
Здравствуйте, adontz, Вы писали:
A>Дана шахматная доска 8х8 клеток A>В левом нижнем углу король A>Он может двигаться вверх, вправо или вверх и вправо по диагонали A>Слолько различных путей у короля из левого нижнего угла в правый верхний если он не совершает более 3 движений подряд в одном и том же направлении ?
А с рекурсией пожалуй покрасивей будет, да и результат посолидней: 12389303
#include <stdio.h>
#include <vector>
using namespace std;
void Step(int x, int y);
void OutputPath();
vector<pair<int, int> > Path;
int N, M, Count;
void main(int argc, char* argv[])
{
if(argc!=3){
printf("argv[1] - Table size\n");
printf("argv[2] - Max step\n");
return;
}
N = atoi(argv[1]);
M = atoi(argv[2]);
Count = 0;
Step(0, 0);
printf("%d\n", Count);
}
void Step(int x, int y)
{
int i;
if(x==N && y==N){
// OutputPath();
Count++;
return;
}
else{
for(i=1; i<=N-x && i<=M; i++){
Path.push_back(pair<int, int>(x + i, y));
Step(x + i, y);
Path.pop_back();
}
for(i=1; i<=N-y && i<=M; i++){
Path.push_back(pair<int, int>(x, y + i));
Step(x, y + i);
Path.pop_back();
}
for(i=1; i<=N-x && i<=N-y && i<=M; i++){
Path.push_back(pair<int, int>(x + i, y + i));
Step(x + i, y + i);
Path.pop_back();
}
}
}
void OutputPath()
{
static int line=0;
printf("%7d: ", ++line);
for(int i=0; i< Path.size(); i++){
printf("(%2d, %2d) ", Path[i].first, Path[i].second);
}
printf("\n");
}
, а никто и не заметил... 
Перекуём баги на фичи!
, только на листочке
