Task: http://informatics.mccme.ru/mod/statements/view3.php?id=255&chapterid=161 What is the horse's path to store? Point path [MAXN]?

vector <pair> path (MAXN)?

int path [MAXN] [MAXN]?

So that later it was possible to record for the neighbors the vertex from which we came (x, y)

Code: http://pastebin.com/RbNNNSbc

Closed due to the fact that the essence of the question is not clear to the participants by Denis , Harry , Vadim Ovchinnikov , pavel , user194374 10 Jan '17 at 6:13 .

Try to write more detailed questions. To get an answer, explain what exactly you see the problem, how to reproduce it, what you want to get as a result, etc. Give an example that clearly demonstrates the problem. If the question can be reformulated according to the rules set out in the certificate , edit it .

  • How do you prefer! ... - Harry
  • @Harry I initially declared via Point path [MAXN], but during the initialization path [horse] = tmp; the compiler produces the error "binary '[': no ​​global operator found it takes type 'Point' ...", tmp here type Point, tmp.x = UNDEF, tmp.y = UNDEF - Koki
  • I would just keep the nodes, and in the node - the coordinates and the previous one, whence it came ... - Harry

1 answer 1

Well, such a simple sketch, well, very far from optimality ...

struct Cell { Cell(int x, int y):x(x),y(y),prev(0),check(false){} int x, y; Cell* prev; bool check; }; int dx[] = { -2, -2, -1, -1, 1, 1, 2, 2 }; int dy[] = { -1, 1, -2, 2, 2, -2, 1, -1 }; int main(int argc, const char * argv[]) { int N; int startx, starty; int stopx, stopy; cin >> N >> startx >> starty >> stopx >> stopy; startx--; starty--; stopx--; stopy--; vector<vector<Cell>> board(N); for(int x = 0; x < N; ++x) { for(int y = 0; y < N; ++y) board[x].push_back(Cell(x,y)); } queue<Cell*> Q; Cell * c = &board[startx][starty]; c->check = true; Q.push(c); while(!Q.empty()) { c = Q.front(); Q.pop(); for(int i = 0; i < 8; ++i) { int x = c->x + dx[i]; int y = c->y + dy[i]; if (x >= 0 && x < N && y >= 0 && y < N) { Cell* q = &board[x][y]; if (q->check) continue; q->check = true; q->prev = c; Q.push(q); if (q->x == stopx && q->y == stopy) { stack<Cell*> S; do { S.push(q); q = q->prev; } while(q); cout << S.size()-1 << endl; while(!S.empty()) { Cell * v = S.top(); S.pop(); cout << v->x+1 << " " << v->y+1 << endl; } return 0; } } } } }