Deswing | Дата: Пятница, 13 Декабря 2013, 02:44 | Сообщение # 1 |
заслуженный участник
Сейчас нет на сайте
| Привет всем! По сути речь идет о алгоритме Дейкстры. Сам я пытался решить, но только под конец понял, что решил далеко не то, что надо было, ведь я получил далеко не самую меньшую сумму весов: Код #include <iostream> #include <stdio.h> #include <time.h> using namespace std;
const int n = 26; const int size = n*n; int* map = new int[size]; FILE* stream;
int pos_read(int x, int y) { return map[y*n+x]; }
void pos_write(int x, int y, int c) { map[y*n+x] = c; }
class Player { private: int x, y; public: int buffer,rec; Player() { x = 0, y = 0, buffer = pos_read(x,y), rec = 0; pos_write(x,y,-1); Logic(n-1,n-1); } void Logic(int kx, int ky) { rec++; if((x>=kx)&&(y>=ky)) { return; } if((y!=ky)&&(x!=kx)) { if((pos_read(x+1,y)>=pos_read(x,y+1))) { y++; buffer+=pos_read(x,y); pos_write(x,y,-1); } else { x++; buffer+=pos_read(x,y); pos_write(x,y,-1); } } else { if(x>=kx) { y++; buffer+=pos_read(x,y); pos_write(x,y,-1); } else { x++; buffer+=pos_read(x,y); pos_write(x,y,-1); } } Logic(kx,ky); } };
int main(void) { srand(time(false)); clock_t t0 = clock(); printf("Generating matrix...\n"); for(int i = 0; i < size; i++) { map[i] = rand()%20+10; } printf("Generated!:\n"); for(int i = 0; i < n; i++) { for(int u = 0; u < n; u++) { cout<<pos_read(u,i)<<" "; } printf("\n"); } printf("Saving matrix...\n"); printf("Trying to open matrix.txt\n"); stream = fopen("matrix.txt","w"); if(stream == NULL) { printf("ERROR: Cannot open matrix.txt\n"); return 1; } else { printf("matrix.txt opened successfully\n"); } for(int y = 0; y < n; y++) { for(int x = 0; x < n; x++) { fprintf(stream,"%d",pos_read(x,y)); fputc(' ',stream); } fputs("\n",stream); } printf("Matrix saved!\n"); fclose(stream); printf("matrix.txt closed successfully\n"); printf("Building path...\n"); Player *A = new Player; printf("Result:\n"); for(int i = 0; i < n; i++) { for(int u = 0; u < n; u++) { cout<<pos_read(u,i)<<" "; } printf("\n"); } printf("Value:%d \n",A->buffer); printf("Recursions:%d \n",A->rec); delete A; printf("Saving the coordinates of moves\n"); stream = fopen("path.txt","w"); for(int y = 0, i = 0; y < n; y++) { for(int x = 0; x < n; x++) { if(pos_read(x,y)==-1) { i++; fprintf(stream,"%d",i); fputc(':',stream); fprintf(stream,"%d",x); fputc(' ',stream); fprintf(stream,"%d",y); fputs("\n",stream); } } } fclose(stream); printf("ALL DONE!\n"); clock_t t1 = clock(); cout<<"Generation time: "<<(double)(t1-t0)/(double)CLOCKS_PER_SEC<<" sec."<<endl; system("PAUSE"); return 0; } В связи с этим начал читать о графах, деревьях... И назрели вопросы: Пусть дана матрица NxN (массив), тогда: 1)Сколькими способами из точки А(x1,y1) можно добраться в точку Б(x2,y2) (при условии, что x1!=x2,y1!=y2, и нельзя ходить в посещенные клеточки. Ходить можно вправо\влево\вниз\вверх и по диагоналям)? 2)Зная кол-во возможных путей можно их каким-то образом перебрать и сохранить сумму в ячейке результирующей матрицы... Как это сделать? Интересует именно обход каждый раз новых путей без повторенийДобавлено (13.12.2013, 02:44) --------------------------------------------- P.S. в моем коде используется рекурсия, т.к. данную задачу по условию нужно решить с её использованием
Сообщение отредактировал Deswing - Пятница, 13 Декабря 2013, 02:42 |
|
| |
GECK | Дата: Пятница, 13 Декабря 2013, 11:30 | Сообщение # 2 |
заслуженный участник
Сейчас нет на сайте
| Ну во-первых это очень странный Дейкстра Больше напоминает жадный покоординатный спуск. Вопрос на засыпку: что именно представляют собой числа в твоей матрице? Дейкстра на вход принимает граф со стоимостью переходов, а не со стоимостью вершин.
Всё гениальное просто. И хреново работает.
|
|
| |
Deswing | Дата: Суббота, 14 Декабря 2013, 02:27 | Сообщение # 3 |
заслуженный участник
Сейчас нет на сайте
| GECK, числа в ячейках - вес соответствующих ячеек. Задача такова: добраться из А в Б, но при этом набрав наименьший вес
|
|
| |