Форум программистов, компьютерный форум CyberForum.ru

Добавить размеры в код "Обход конем" - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.92
Катерька
0 / 0 / 0
Регистрация: 07.01.2013
Сообщений: 32
15.01.2013, 23:27     Добавить размеры в код "Обход конем" #1
Господа,решила в новой теме попросить помощи.есть код
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <stdio.h>
#include <conio.h>
#define  size_row 10
#define  size_col 10
 
 
 
int main(void)
{
    
     int Ni=0; 
     int Nk=300;
     int y=255; 
     int n=253; 
     int s=0; 
     int e=254;
     int i,j;
     int R[size_row][size_col]= {            {s,y,y,y,y,y,y,n,n,n},
                                               {n,y,n,n,n,y,y,n,n,n},
                                                {y,y,n,n,n,y,n,n,n,n},
                                                {y,n,e,y,y,y,n,n,n,n},
                                               {y,y,y,n,n,n,n,n,n,n},
                                            {n,n,n,n,n,n,n,n,n,n},
                                               {n,n,n,n,n,n,n,n,n,n},
                                                {n,n,n,n,n,n,n,n,n,n},
                                                {n,n,n,n,n,n,n,n,n,n},
                                                {n,n,n,n,n,n,n,n,n,n} };
 
printf("labyrint pered algoritmem::" "\n \n");
   for (i=0; i < size_row; i++)
{
   for (j=0; j < size_col; j++)
   printf("%d\t",R[i][j]);
}
 
/*vlnovy algoritmus*/
while (Ni < Nk)
{
   for (i=0; i < size_row; i++)
   {
     for (j=0; j < size_col; j++)
     /*spousteni*/
     if (R[i][j]==Ni)
     {
         if (R[i][j+1]==255)
            R[i][j+1]=Ni+1;
         if (R[i][j-1]==255)
            R[i][j-1]=Ni+1;
         if (R[i+1][j]==255)
            R[i+1][j]=Ni+1;
         if (R[i-1][j]==255)
            R[i-1][j]=Ni+1;
         if ((R[i+1][j]==254) || (R[i-1][j]==254) || (R[i][j+1]==254) || (R[i][j-1]==254))
         {  
            //printf(
            //getch(); 
            //return 0; 
            //break;
          
         }
      }
   }
Ni++;
}
 
   printf("\n\n");
 
 
printf ("labyrint posle algoritma:: \n \n");
for (i=0; i < size_row; i++)
{
   for (j=0; j < size_col; j++)
   printf("%d\t", R[i][j]);
}
 
   getch();
   return 0;
}
это обход конем по шахматной доске.к нему нужно прилепить следующее:
-размеры шахматной доски.
-координаты конечного поля.
как это воплотить в жизнь?

Спасибо.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2911 / 1340 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
23.01.2013, 23:56     Добавить размеры в код "Обход конем" #21
Я тут вот чего придумал. Поскольку исходная точка одна, задача сводится к помеси алгоритма Дейкстры с волновым алгоритмом. Надо просто заполнить все возможные минимальные варианты хода коня по всем возможным клеткам, начиная с исходной. Т.е. не надо ни сложных матриц смежности, ни структур типа стек.

Простейшая реализация через рекурсию.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
 
int **newMatrix(int height, int width, int value) {
  int i, j;
  int **matrix = (int**)malloc(sizeof(int*) * height);
  for (i = 0; i < height; ++i) {
    matrix[i] = (int*)malloc(sizeof(int) * width);
    for (j = 0; j < width; ++j) {
      matrix[i][j] = value;
    }
  }
  return matrix;
}
 
void deleteMatrix(int **matrix, int height) {
  int i;
  for (i = 0; i < height; ++i)
    free(matrix[i]);
  free(matrix);
}
 
void fillMatrix(int **matrix, int height, int width, int y, int x, int value) {
  if (y > -1 && y < height && x > -1 && x < width && (matrix[y][x] > value || matrix[y][x] < 0)) {
    matrix[y][x] = value++;
    fillMatrix(matrix, height, width, y - 1, x - 2, value);
    fillMatrix(matrix, height, width, y + 1, x - 2, value);
    fillMatrix(matrix, height, width, y - 1, x + 2, value);
    fillMatrix(matrix, height, width, y + 1, x + 2, value);
    fillMatrix(matrix, height, width, y - 2, x - 1, value);
    fillMatrix(matrix, height, width, y - 2, x + 1, value);
    fillMatrix(matrix, height, width, y + 2, x - 1, value);
    fillMatrix(matrix, height, width, y + 2, x + 1, value);
  }
}
 
void printMatrix(int **matrix, int height, int width) {
  int i, j;
  for (i = 0; i < height; ++i) {
    for (j = 0; j < width; ++j) {
      printf("%3d", matrix[i][j]);
    }
    printf("\n");
  }
}
 
int printPathRecursive(int **matrix, int height, int width, int y, int x,
  int value) {
  if (x < 0 || x >= width || y < 0 || y >= height || matrix[y][x] != value)
    return 0;
  
  printf("%d/%d ", y, x);
  if (matrix[y][x] > 0) {
    return
      printPathRecursive(matrix, height, width, y - 2, x + 1, value - 1) ||
      printPathRecursive(matrix, height, width, y - 2, x - 1, value - 1) ||
      printPathRecursive(matrix, height, width, y + 2, x + 1, value - 1) ||
      printPathRecursive(matrix, height, width, y + 2, x - 1, value - 1) ||
      printPathRecursive(matrix, height, width, y + 1, x + 2, value - 1) ||
      printPathRecursive(matrix, height, width, y - 1, x + 2, value - 1) ||
      printPathRecursive(matrix, height, width, y + 1, x - 2, value - 1) ||
      printPathRecursive(matrix, height, width, y - 1, x - 2, value - 1);
  } else if (matrix[y][x] == 0) {
    printf("\n");
    return 1;
  } else {
    printf("no path.\n");    
    return 0;
  }
}
 
int printPath(int **matrix, int height, int width, int y, int x) {
  printf("Path from %d/%d: ", y, x);
  printPathRecursive(matrix, height, width, y, x, matrix[y][x]);
}
 
int main(int argc, char *argv[])
{
  srand(time(0));
 
  int height = 12;
  int width = 12;
  
  int **matrix = newMatrix(height, width, -1);
 
  int y = rand() % height;
  int x = rand() % width;
  fillMatrix(matrix, height, width, y, x, 0);
 
  printMatrix(matrix, height, width);
 
  int i, j;
  for (i = 0; i < height; ++i)
    for (j = 0; j < width; ++j)
      printPath(matrix, height, width, i, j);
 
  deleteMatrix(matrix, height);
  
  printf("Press enter to continue ...");
  getchar();    
  return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
UserAK
70 / 70 / 4
Регистрация: 25.12.2012
Сообщений: 189
Записей в блоге: 2
24.01.2013, 02:24     Добавить размеры в код "Обход конем" #22
вот вариант с одномерным массивом
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
using namespace std;
 
int *ChessBoard, BoardHeight, BoardWidth, BoardSize, StartR, StartC, StartI; // шахматная доска и всё такое
int *GStack, GSP; // динамический массив выполняет роль глобального стека
 
// сдужебные инлайн функции, что бы работать с одномерным массивом как с матрицей
inline bool CellExists(int &R, int &C){
    return (R >= 0 && C >= 0 && R < BoardHeight && C < BoardWidth );
}
 
inline int CellIndex(int &R, int &C){
    return (R * BoardWidth + C);
}
 
inline int &ChessBoardCell(int &R, int &C){
    return ChessBoard[CellIndex(R, C)];
}
 
inline int CellR(int &I){
    return I / BoardWidth;
}
 
inline int CellC(int &I){
    return I % BoardWidth;
}
 
// заполнение ячеек матрицы
void FillBoard()
{
    static const int offset[8][2] = {{ 1, 2},{ 2, 1},{ 2,-1},{ 1,-2},{-1,-2},{-2,-1},{-2, 1},{-1, 2}};
    int SP(0), *Stack = new int[BoardSize]; // временный массив выполняет роль локального стека
    int I, R, C, R1, C1;
    while( GSP > 0 ){
        I = GStack[GSP--]; //pop
        R = CellR(I);
        C = CellC(I);
        for(unsigned i=0; i<8; i++){
            R1 = R + offset[i][0];
            C1 = C + offset[i][1];
            if( CellExists(R1, C1) && ChessBoardCell(R1, C1) == -1 ){
                ChessBoardCell(R1, C1) = I;
                Stack[++SP] = CellIndex(R1, C1); //push
            }
        }
    }
    while( SP > 0 ){
        GStack[++GSP] = Stack[SP--]; // push pop
    }
    delete[] Stack;
}
 
void GetPass(int pos)
{
    GSP = 0;
    int prevpos = ChessBoard[pos];
    do{
        GStack[++GSP] = prevpos;
        prevpos = ChessBoard[prevpos];
    }while( prevpos != StartI );
}
 
int main()
{
    // ввод исходных данных
    do{
        system("cls");
        cout<<"Input chessboard height width : ";
        cin>>BoardHeight>>BoardWidth;
    }while( BoardHeight < 1 || BoardWidth < 1 );
    BoardSize = BoardHeight*BoardWidth;
    do{
        system("cls");
        std::cout<<"Chessboard "<<BoardHeight<<"x"<<BoardWidth<<" size "<<BoardSize
            <<"\nInput start cell R C : ";
        std::cin>>StartR>>StartC;
    }while(!CellExists(StartR, StartC));
    
    // создание и заполнение матрицы
    ChessBoard = new int[BoardSize];
    for( int i=0; i<BoardSize; i++ ) ChessBoard[i] = -1;
    StartI = CellIndex(StartR, StartC);
    ChessBoardCell(StartR, StartC) = StartI;
    GStack = new int[BoardSize];
    GSP = 0;
    GStack[++GSP] = StartI; //push
    while(GSP > 0){
        FillBoard();
    }
 
    // вывод последовательностей ходов в каждую точку
    int pos;
    for(int i=0; i<BoardSize; i++){
        cout<<CellR(StartI)<<","<<CellC(StartI)<<"->";
        GetPass(i);
        while(GSP > 0){
            pos = GStack[GSP--];
            cout<<CellR(pos)<<","<<CellC(pos)<<"->";
        }
        cout<<CellR(i)<<","<<CellC(i)<<endl;
    }
    delete[] GStack;
 
    system("pause");
    delete[] ChessBoard;
    return 0;
}
Добавлено через 33 минуты
Катерька
0 / 0 / 0
Регистрация: 07.01.2013
Сообщений: 32
24.01.2013, 03:19  [ТС]     Добавить размеры в код "Обход конем" #23
lemegeton, вы чудесны,код просто идеально подходит))
он все не отстанет с загрузкой размеров и координатов..можно ли с помощью printf использовать height,wigth,координаты y и x для загрузки?

Добавлено через 44 секунды
UserAK, спасибо и Вам,к сожалению,препод поставил строгий запрет на С++...

Добавлено через 15 минут
попросил загрузить с помощью scanf

Добавлено через 12 минут
..эээ..через printf понятно,как это сделать,а тут..или совместно с printf делать и scanf,чтобы он просил вводить данные?уфф..помогите последний раз,я отвяжусь,любезный
lemegeton?
UserAK
70 / 70 / 4
Регистрация: 25.12.2012
Сообщений: 189
Записей в блоге: 2
24.01.2013, 08:24     Добавить размеры в код "Обход конем" #24
вот через printf() и scanf()
без ссылок и new delete
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <memory.h>
 
const int offset[8][2] = {{ 1, 2},{ 2, 1},{ 2,-1},{ 1,-2},{-1,-2},{-2,-1},{-2, 1},{-1, 2}}; // смещения для ходов
int *ChessBoard, BoardHeight, BoardWidth, BoardSize, StartR, StartC, StartI; // шахматная доска и всё такое
int *GStack, GSP; // массив выполняет роль глобального стека
 
// служебные функции, что бы работать с одномерным массивом как с матрицей
bool CellExists(int R, int C){
    return (R >= 0 && C >= 0 && R < BoardHeight && C < BoardWidth );
}
 
int CellIndex(int R, int C){
    return (R * BoardWidth + C);
}
 
int GetChessBoardCell(int R, int C){
    return ChessBoard[CellIndex(R, C)];
}
 
void SetChessBoardCell(int R, int C, int val){
    ChessBoard[CellIndex(R, C)] = val;
}
 
int CellR(int I){
    return I / BoardWidth;
}
 
int CellC(int I){
    return I % BoardWidth;
}
 
// заполнение массива каждая ячейка содержит адрес предыдущей
void FillBoard()
{
    int SP, *Stack, I, R, C, R1, C1, i;
    Stack = (int*)malloc(sizeof(int)*BoardSize); // временный массив выполняет роль локального стека
    SP = 0;
    while( GSP > 0 ){
        I = GStack[GSP--]; //pop
        R = CellR(I);
        C = CellC(I);
        for(i=0; i<8; i++){
            R1 = R + offset[i][0];
            C1 = C + offset[i][1];
            if( CellExists(R1, C1) && GetChessBoardCell(R1, C1) == -1 ){
                SetChessBoardCell(R1, C1, I);
                Stack[++SP] = CellIndex(R1, C1); //push
            }
        }
    }
    while( SP > 0 ){
        GStack[++GSP] = Stack[SP--]; // push pop
    }
    free(Stack);
}
 
// извлечение последовательности ходов
void GetPass(int pos)
{
    GSP = 0;
    int prevpos = ChessBoard[pos];
    while( prevpos != StartI ){
        GStack[++GSP] = prevpos;
        prevpos = ChessBoard[prevpos];
    }
}
 
int main()
{
    // ввод исходных данных
    do{
        printf("Input chessboard height width : ");
        scanf("%i %i", &BoardHeight, &BoardWidth);
    }while( BoardHeight < 1 || BoardWidth < 1 );
    BoardSize = BoardHeight*BoardWidth;
    do{
        printf("Input start cell R C : ");
        scanf("%i %i", &StartR, &StartC);
    }while(!CellExists(StartR, StartC));
    
    // создание и заполнение массива
    ChessBoard = (int*) malloc(sizeof(int)*BoardSize);
    memset(ChessBoard, -1, sizeof(int)*BoardSize);
    StartI = CellIndex(StartR, StartC);
    SetChessBoardCell(StartR, StartC, StartI);
    GStack = (int*) malloc(sizeof(int)*BoardSize);
    GSP = 0;
    GStack[++GSP] = StartI; //push
    while(GSP > 0){
        FillBoard();
    }
 
    // вывод последовательностей ходов в каждую точку
    int pos, i;
    for(i=0; i<BoardSize; i++){
        if(i != StartI){
            printf("%d,%d->", CellR(StartI), CellC(StartI) );
            GetPass(i);
            while(GSP > 0){
                pos = GStack[GSP--];
                printf("%d,%d->", CellR(pos), CellC(pos));
            }
        }
        printf("%d,%d\n", CellR(i), CellC(i));
    }
 
    free(GStack);
    free(ChessBoard);
    getch();
    return 0;
}
Добавлено через 21 минуту
если использовать макросы, то получается так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <memory.h>
 
// макросы, что бы работать с одномерным массивом как с матрицей
#define CellExists(_R, _C) (_R >= 0 && _C >= 0 && _R < BoardHeight && _C < BoardWidth)
#define CellIndex(_R, _C) (_R * BoardWidth + _C)
#define ChessBoardCell(_R, _C) ChessBoard[CellIndex(_R, _C)]
#define CellR(_I) (_I / BoardWidth)
#define CellC(_I) (_I % BoardWidth)
 
// глобальные переменные и константы
const int offset[8][2] = {{ 1, 2},{ 2, 1},{ 2,-1},{ 1,-2},{-1,-2},{-2,-1},{-2, 1},{-1, 2}}; // смещения для ходов
int *ChessBoard, BoardHeight, BoardWidth, BoardSize, StartR, StartC, StartI; // шахматная доска и всё такое
int *GStack, GSP; // массив выполняет роль глобального стека
 
// заполнение массива каждая ячейка содержит адрес предыдущей
void FillBoard()
{
    int SP, *Stack, I, R, C, R1, C1, pass;
    Stack = (int*)malloc(sizeof(int)*BoardSize); // временный массив выполняет роль локального стека
    SP = 0;
    while( GSP > 0 ){
        I = GStack[GSP--]; //pop
        R = CellR(I);
        C = CellC(I);
        for(pass=0; pass<8; pass++){
            R1 = R + offset[pass][0];
            C1 = C + offset[pass][1];
            if( CellExists(R1, C1) && ChessBoardCell(R1, C1) == -1 ){
                ChessBoardCell(R1, C1) = I;
                Stack[++SP] = CellIndex(R1, C1); //push
            }
        }
    }
    while( SP > 0 ){
        GStack[++GSP] = Stack[SP--]; // push pop
    }
    free(Stack);
}
 
// извлечение последовательности ходов
void GetPass(int pos)
{
    GSP = 0;
    int prevpos = ChessBoard[pos];
    while( prevpos != StartI ){
        GStack[++GSP] = prevpos;
        prevpos = ChessBoard[prevpos];
    }
}
 
int main()
{
    // ввод исходных данных
    do{
        printf("Input chessboard height width : ");
        scanf("%i %i", &BoardHeight, &BoardWidth);
    }while( BoardHeight < 1 || BoardWidth < 1 );
    BoardSize = BoardHeight*BoardWidth;
    do{
        printf("Input start cell R C : ");
        scanf("%i %i", &StartR, &StartC);
    }while(!CellExists(StartR, StartC));
    
    // создание и заполнение массива
    ChessBoard = (int*) malloc(sizeof(int)*BoardSize);
    memset(ChessBoard, -1, sizeof(int)*BoardSize);
    StartI = CellIndex(StartR, StartC);
    ChessBoardCell(StartR, StartC) = StartI;
    GStack = (int*) malloc(sizeof(int)*BoardSize);
    GSP = 0;
    GStack[++GSP] = StartI; //push
    while(GSP > 0){
        FillBoard();
    }
 
    // вывод последовательностей ходов в каждую точку
    int pos, i;
    for(i=0; i<BoardSize; i++){
        if(i != StartI){
            printf("%d,%d->", CellR(StartI), CellC(StartI) );
            GetPass(i);
            while(GSP > 0){
                pos = GStack[GSP--];
                printf("%d,%d->", CellR(pos), CellC(pos));
            }
        }
        printf("%d,%d\n", CellR(i), CellC(i));
    }
 
    free(GStack);
    free(ChessBoard);
    getch();
    return 0;
}
lemegeton
 Аватар для lemegeton
2911 / 1340 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
24.01.2013, 08:25     Добавить размеры в код "Обход конем" #25
Цитата Сообщение от Катерька Посмотреть сообщение
он все не отстанет с загрузкой размеров и координатов..можно ли с помощью printf использовать height,wigth,координаты y и x для загрузки?
Да, конечно. Переменные height, width, x и y вполне можно считывать с консоли вместо инициализации константами. Все будет работать.

Вот пример ввода. Сделайте по аналогии.
Обратите внимание на амперсанд перед width в scanf'е. Он очень важен.
C
1
2
3
  int width;
  printf("Enter width: ");
  scanf("%d", &width);
UserAK
70 / 70 / 4
Регистрация: 25.12.2012
Сообщений: 189
Записей в блоге: 2
24.01.2013, 08:28     Добавить размеры в код "Обход конем" #26
ну вот вроде ничего от C++ не осталось

Добавлено через 1 минуту
lemegeton, посмотрите плиз если не сложно, мой последний код в С будет работать? вроде ничего нет от С++ там?
lemegeton
 Аватар для lemegeton
2911 / 1340 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
24.01.2013, 08:45     Добавить размеры в код "Обход конем" #27
Цитата Сообщение от UserAK Посмотреть сообщение
lemegeton, посмотрите плиз если не сложно, мой последний код в С будет работать? вроде ничего нет от С++ там?
Компилируется, выдает результат.
Падает, если нет пути до точки, попробуйте поле размером 3х3.

Не по теме:

Конечно, решение через стек более универсально, чем через рекурсию, но его сложнее понять.

UserAK
70 / 70 / 4
Регистрация: 25.12.2012
Сообщений: 189
Записей в блоге: 2
24.01.2013, 09:12     Добавить размеры в код "Обход конем" #28
вот теперь не падает и пишет если нет пути, спасибо )
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <memory.h>
 
// макросы, что бы работать с одномерным массивом как с матрицей
#define CellExists(_R, _C) (_R >= 0 && _C >= 0 && _R < BoardHeight && _C < BoardWidth)
#define CellIndex(_R, _C) (_R * BoardWidth + _C)
#define ChessBoardCell(_R, _C) ChessBoard[CellIndex(_R, _C)]
#define CellR(_I) (_I / BoardWidth)
#define CellC(_I) (_I % BoardWidth)
 
// глобальные переменные и константы
const int offset[8][2] = {{ 1, 2},{ 2, 1},{ 2,-1},{ 1,-2},{-1,-2},{-2,-1},{-2, 1},{-1, 2}}; // смещения для ходов
int *ChessBoard, BoardHeight, BoardWidth, BoardSize, StartR, StartC, StartI; // шахматная доска и всё такое
int *GStack, GSP; // массив выполняет роль глобального стека
 
// заполнение массива каждая ячейка содержит адрес предыдущей
void FillBoard()
{
    int SP, *Stack, I, R, C, R1, C1, pass;
    Stack = (int*)malloc(sizeof(int)*BoardSize); // временный массив выполняет роль локального стека
    SP = 0;
    while( GSP > 0 ){
        I = GStack[GSP--]; //pop
        R = CellR(I);
        C = CellC(I);
        for(pass=0; pass<8; pass++){
            R1 = R + offset[pass][0];
            C1 = C + offset[pass][1];
            if( CellExists(R1, C1) && ChessBoardCell(R1, C1) == -1 ){
                ChessBoardCell(R1, C1) = I;
                Stack[++SP] = CellIndex(R1, C1); //push
            }
        }
    }
    while( SP > 0 ){
        GStack[++GSP] = Stack[SP--]; // push pop
    }
    free(Stack);
}
 
// извлечение последовательности ходов
void GetPass(int pos)
{
    GSP = 0;
    int prevpos = ChessBoard[pos];
    while( prevpos != StartI && prevpos >= 0){
        GStack[++GSP] = prevpos;
        prevpos = ChessBoard[prevpos];
    }
}
 
int main()
{
    // ввод исходных данных
    do{
        printf("Input chessboard height width : ");
        scanf("%i %i", &BoardHeight, &BoardWidth);
    }while( BoardHeight < 1 || BoardWidth < 1 );
    BoardSize = BoardHeight*BoardWidth;
    do{
        printf("Input start cell R C : ");
        scanf("%i %i", &StartR, &StartC);
    }while(!CellExists(StartR, StartC));
    
    // создание и заполнение массива
    ChessBoard = (int*) malloc(sizeof(int)*BoardSize);
    memset(ChessBoard, -1, sizeof(int)*BoardSize);
    StartI = CellIndex(StartR, StartC);
    ChessBoardCell(StartR, StartC) = StartI;
    GStack = (int*) malloc(sizeof(int)*BoardSize);
    GSP = 0;
    GStack[++GSP] = StartI; //push
    while(GSP > 0){
        FillBoard();
    }
 
    // вывод последовательностей ходов в каждую точку
    int pos, i;
    for(i=0; i<BoardSize; i++){
        if( ChessBoard[i] == -1 ){
            printf("No path to %d,%d\n", CellR(i), CellC(i) );
            continue;
        }
        if(i != StartI){
            printf("%d,%d->", CellR(StartI), CellC(StartI) );
            GetPass(i);
            while(GSP > 0){
                pos = GStack[GSP--];
                printf("%d,%d->", CellR(pos), CellC(pos));
            }
        }
        printf("%d,%d\n", CellR(i), CellC(i));
    }
 
    free(GStack);
    free(ChessBoard);
    getch();
    return 0;
}
Добавлено через 11 минут
просто я это написал, чтобы показать как заменить шаблонный stack<int> массивом, обойтись без рекурсии и заодно использовать одномерный массив вместо матрицы. вроде получилось, ми доволен
lemegeton
 Аватар для lemegeton
2911 / 1340 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
24.01.2013, 09:18     Добавить размеры в код "Обход конем" #29
Цитата Сообщение от UserAK Посмотреть сообщение
просто я это написал, чтобы показать как заменить шаблонный stack<int> массивом, обойтись без рекурсии и заодно использовать одномерный массив вместо матрицы. вроде получилось, ми доволен
Ага, только через код теперь не продраться без пол-банки. )
Еще надо бы от глобальных переменных отказаться.
UserAK
70 / 70 / 4
Регистрация: 25.12.2012
Сообщений: 189
Записей в блоге: 2
24.01.2013, 09:31     Добавить размеры в код "Обход конем" #30
что верно, то верно
это всё ради того, что бы было как можно меньше параметров всяких у функций вот даже макросов налепил

Добавлено через 2 минуты
сначала сделал с рекурсией, но ввёл что-то вроде 100х100 и стэк лопнул. тогда вот и решил извратиться

Добавлено через 2 минуты
и решил не таскать туда-сюда эту несчастную матрицу из функции в функцию, сделал глобальной, да и всё остальное заодно уж
Катерька
0 / 0 / 0
Регистрация: 07.01.2013
Сообщений: 32
24.01.2013, 18:00  [ТС]     Добавить размеры в код "Обход конем" #31
Цитата Сообщение от lemegeton Посмотреть сообщение
Да, конечно. Переменные height, width, x и y вполне можно считывать с консоли вместо инициализации константами. Все будет работать.

Вот пример ввода. Сделайте по аналогии.
Обратите внимание на амперсанд перед width в scanf'е. Он очень важен.
C
1
2
3
  int width;
  printf("Enter width: ");
  scanf("%d", &width);
я так у себя и сделала,только вот значений потребовалось вводить больше,чем мне показалось нужным.value ведь тоже нужно инициализировать?

Добавлено через 2 минуты
а каждый раз int писать по идее не нужно,ведь есть строка,которая относит все величины к типу int
lemegeton
 Аватар для lemegeton
2911 / 1340 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
24.01.2013, 19:27     Добавить размеры в код "Обход конем" #32
Цитата Сообщение от Катерька Посмотреть сообщение
value ведь тоже нужно инициализировать?
Нет-нет. У него "магическое" начальное значение 0. Не надо его вводить. Вообще, суть этого value -- минимальное количество ходов до клетки.

Вообще, я бы на вашем месте сделал функцию вроде такой:
C
1
2
3
4
5
6
int readInteger(const char *message) {
  int result;
  printf("%s: ", message);
  scanf("%d", &result);
  return result;
};
Ну и потом с её помощью проинициализировал все четыре переменные.
C
1
2
3
4
  int height = readInteger("Enter field height");
  int width = readInteger("Enter field width");
  int y = readInteger("Enter start row");;
  int x = readInteger("Enter start column");;
И все, никого больше никуда вводить не надо.
Катерька
0 / 0 / 0
Регистрация: 07.01.2013
Сообщений: 32
25.01.2013, 00:19  [ТС]     Добавить размеры в код "Обход конем" #33
Премногоуважаемый lemegeton, послала ему вот это
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
 
 
 
 
int **newMatrix(int height, int width, int value) {
    
    
    
    
  int i, j;
  int **matrix = (int**)malloc(sizeof(int*) * height);
  for (i = 0; i < height; ++i) {
    matrix[i] = (int*)malloc(sizeof(int) * width);
    for (j = 0; j < width; ++j) {
      matrix[i][j] = value;
    }
  }
  return matrix;
}
 
 
 
 
void deleteMatrix(int **matrix, int height) {
  int i;
  for (i = 0; i < height; ++i)
    free(matrix[i]);
  free(matrix);
}
 
void fillMatrix(int **matrix, int height, int width, int y, int x, int value) {
 
 
 
   
  
    
    
  if (y > -1 && y < height && x > -1 && x < width && (matrix[y][x] > value || matrix[y][x] < 0)) {
    matrix[y][x] = value++;
    fillMatrix(matrix, height, width, y - 1, x - 2, value);
    fillMatrix(matrix, height, width, y + 1, x - 2, value);
    fillMatrix(matrix, height, width, y - 1, x + 2, value);
    fillMatrix(matrix, height, width, y + 1, x + 2, value);
    fillMatrix(matrix, height, width, y - 2, x - 1, value);
    fillMatrix(matrix, height, width, y - 2, x + 1, value);
    fillMatrix(matrix, height, width, y + 2, x - 1, value);
    fillMatrix(matrix, height, width, y + 2, x + 1, value);
  }
}
 
void printMatrix(int **matrix, int height, int width) {
  int i, j;
  for (i = 0; i < height; ++i) {
    for (j = 0; j < width; ++j) {
      printf("%3d", matrix[i][j]);
    }
    printf("\n");
  }
}
 
int printPathRecursive(int **matrix, int height, int width, int y, int x,
  int value) {
  if (x < 0 || x >= width || y < 0 || y >= height || matrix[y][x] != value)
    return 0;
  
  printf("%d/%d ", y, x);
  if (matrix[y][x] > 0) {
    return
      printPathRecursive(matrix, height, width, y - 2, x + 1, value - 1) ||
      printPathRecursive(matrix, height, width, y - 2, x - 1, value - 1) ||
      printPathRecursive(matrix, height, width, y + 2, x + 1, value - 1) ||
      printPathRecursive(matrix, height, width, y + 2, x - 1, value - 1) ||
      printPathRecursive(matrix, height, width, y + 1, x + 2, value - 1) ||
      printPathRecursive(matrix, height, width, y - 1, x + 2, value - 1) ||
      printPathRecursive(matrix, height, width, y + 1, x - 2, value - 1) ||
      printPathRecursive(matrix, height, width, y - 1, x - 2, value - 1);  } 
      
      else if (matrix[y][x] == 0) {
    printf("\n");
    return 1;
        }
    
     else {
    printf("no path.\n");    
    return 0;
  }
}
 
 
int printPath(int **matrix, int height, int width, int y, int x) {
  printf("Path from %d/%d: ", y, x);
  printPathRecursive(matrix, height, width, y, x, matrix[y][x]);
}
 
int main(int argc, char *argv[])
{
    
int readInteger(const char *message) {
  int result;
  
  printf("%s: ", message);
  scanf("%d", &result);
  
  return result;
  
   };
    
    {int height = readInteger("Enter field height");
  int width = readInteger("Enter field width");
  int y = readInteger("Enter start row");;
  int x = readInteger("Enter start column");;
    }
   
  srand(time(0));
 
  int height = 12;
  int width = 12;
  
  int **matrix = newMatrix(height, width, -1);
 
  int y = rand() % height;
  int x = rand() % width;
  fillMatrix(matrix, height, width, y, x, 0);
 
  printMatrix(matrix, height, width);
 
  int i, j;
  for (i = 0; i < height; ++i)
    for (j = 0; j < width; ++j)
      printPath(matrix, height, width, i, j);
 
  deleteMatrix(matrix, height);
  
  printf("Press enter to continue ...");
  getchar();    
  return 0;
}
сказал,что так это не работает.что я делаю не так?

Добавлено через 44 секунды
код вставила Ваш..чтобы инициализировал переменные с помощью scanf.или я даже это неправильно сделала?..
lemegeton
 Аватар для lemegeton
2911 / 1340 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
25.01.2013, 00:52     Добавить размеры в код "Обход конем" #34
Ыыы... Оно компилируется.

Цитата Сообщение от Катерька Посмотреть сообщение
сказал,что так это не работает.что я делаю не так?
Много всего. Я, пожалуй, не стану даже пытаться объяснить.

Цитата Сообщение от Катерька Посмотреть сообщение
код вставила Ваш..чтобы инициализировал переменные с помощью scanf.или я даже это неправильно сделала?..
Вы вообще проверяете код перед тем, как отсылать? Надо проверять. Собирайте, запускайте. Мало ли, что я вам пришлю. Обфускация и стеганография -- штуки мощные.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdio.h>
 
int **newMatrix(int height, int width, int value) {
  int i, j;
  int **matrix = (int**)malloc(sizeof(int*) * height);
  for (i = 0; i < height; ++i) {
    matrix[i] = (int*)malloc(sizeof(int) * width);
    for (j = 0; j < width; ++j) {
      matrix[i][j] = value;
    }
  }
  return matrix;
}
 
void deleteMatrix(int **matrix, int height) {
  int i;
  for (i = 0; i < height; ++i)
    free(matrix[i]);
  free(matrix);
}
 
void fillMatrix(int **matrix, int height, int width, int y, int x, int value) {
  if (y > -1 && y < height && x > -1 && x < width &&
    (matrix[y][x] > value || matrix[y][x] < 0)) {
    matrix[y][x] = value++;
    fillMatrix(matrix, height, width, y - 1, x - 2, value);
    fillMatrix(matrix, height, width, y + 1, x - 2, value);
    fillMatrix(matrix, height, width, y - 1, x + 2, value);
    fillMatrix(matrix, height, width, y + 1, x + 2, value);
    fillMatrix(matrix, height, width, y - 2, x - 1, value);
    fillMatrix(matrix, height, width, y - 2, x + 1, value);
    fillMatrix(matrix, height, width, y + 2, x - 1, value);
    fillMatrix(matrix, height, width, y + 2, x + 1, value);
  }
}
 
void printMatrix(int **matrix, int height, int width) {
  int i, j;
  for (i = 0; i < height; ++i) {
    for (j = 0; j < width; ++j) {
      printf("%3d", matrix[i][j]);
    }
    printf("\n");
  }
}
 
int printPathRecursive(int **matrix, int height, int width, int y, int x,
  int value) {
  if (x < 0 || x >= width || y < 0 || y >= height || matrix[y][x] != value)
    return 0;
  
  printf("%d/%d ", y, x);
  if (matrix[y][x] > 0) {
    return
      printPathRecursive(matrix, height, width, y - 2, x + 1, value - 1) ||
      printPathRecursive(matrix, height, width, y - 2, x - 1, value - 1) ||
      printPathRecursive(matrix, height, width, y + 2, x + 1, value - 1) ||
      printPathRecursive(matrix, height, width, y + 2, x - 1, value - 1) ||
      printPathRecursive(matrix, height, width, y + 1, x + 2, value - 1) ||
      printPathRecursive(matrix, height, width, y - 1, x + 2, value - 1) ||
      printPathRecursive(matrix, height, width, y + 1, x - 2, value - 1) ||
      printPathRecursive(matrix, height, width, y - 1, x - 2, value - 1);
  } else if (matrix[y][x] == 0) {
    printf("\n");
    return 1;
  } else {
    printf("no path.\n");    
    return 0;
  }
}
 
int printPath(int **matrix, int height, int width, int y, int x) {
  printf("Path from %d/%d: ", y, x);
  printPathRecursive(matrix, height, width, y, x, matrix[y][x]);
}
 
int readInteger(const char *message) {
  int result;
  printf("%s", message);
  scanf("%d", &result);
  return result;
}
 
int main(int argc, char *argv[])
{
  int height = readInteger("Enter height of field: ");
  int width = readInteger("Enter width of field: ");;
  int y = readInteger("Enter starting row: ");;
  int x = readInteger("Enter starting column: ");;
 
  int **matrix = newMatrix(height, width, -1);
 
  fillMatrix(matrix, height, width, y, x, 0);
 
  printMatrix(matrix, height, width);
 
  int i, j;
  for (i = 0; i < height; ++i)
    for (j = 0; j < width; ++j)
      printPath(matrix, height, width, i, j);
 
  deleteMatrix(matrix, height);
  
  printf("Press enter to continue ...");
  getchar();
  getchar();
  return 0;
}
Чисто из любопытства, на кого вы учитесь, что вам дают такие сложные задачи?
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4928 / 2671 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
25.01.2013, 01:04     Добавить размеры в код "Обход конем" #35
Цитата Сообщение от lemegeton Посмотреть сообщение
Чисто из любопытства, на кого вы учитесь, что вам дают такие сложные задачи?
У меня во втором семестре было. Рекурсивный и нерекурсивный алгоритмы обхода доски конем + размеры доски задавались с клавиатуры.
небритый еж
0 / 0 / 0
Регистрация: 24.01.2013
Сообщений: 49
25.01.2013, 01:12     Добавить размеры в код "Обход конем" #36
lemegeton, не поверите,специальность совсем не связана с программированием,но предмет обязательный.мало того,еще в следующем семестре будет С++.Так что готовьтесь,я скоро буду )))
факультет ядерной физики,специальность связана с радиацией.лол,да?казалось бы,к чему оно нужно.
Катерька
0 / 0 / 0
Регистрация: 07.01.2013
Сообщений: 32
25.01.2013, 01:16  [ТС]     Добавить размеры в код "Обход конем" #37
прошу прощения,не вышла из аккаунта,сосед по комнате тоже на форуме этом сидит,свою задачку ищет))общажные дела.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4928 / 2671 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
25.01.2013, 01:16     Добавить размеры в код "Обход конем" #38
небритый еж, затем же, зачем и программистам ядерная или квантовая физика.
Чтоб было общее развитие и мы были друг с другом на одной волне
Катерька
0 / 0 / 0
Регистрация: 07.01.2013
Сообщений: 32
25.01.2013, 01:22  [ТС]     Добавить размеры в код "Обход конем" #39
MrGluck, это мой пост,я пометила,что с чужого аккаунта просто написала))
ну знаете..с компьютером я разбираюсь отлично,но этого недостаточно видимо.мало того,что был на прошлом курсе паскаль,так еще в этом году всунули С и С++. То есть приеду я куда-нибудь с проверкой замерять загрязненность почвы,а если работы мало окажется,то где-то на дому смогу программку написать требующим..за небольшую плату.так чтоле.Мне физика гораздо интереснее.А программирование я просто уважаю.я с ним на Вы.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.01.2013, 02:00     Добавить размеры в код "Обход конем"
Еще ссылки по теме:

Задача "Тур конем" C++
Разница между понятиями "Обход в прямом направлении" и "Итерационный прямой обход" C++
Двумерный массив: Добавить методы "ДайЗначениеЯчейки", "УстановиЗначениеЯчейки" C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4928 / 2671 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
25.01.2013, 02:00     Добавить размеры в код "Обход конем" #40
Катерька, захотите програмку какую-нибудь написать для подсчета своего маленького коллайдера - запрограммируете, знаний вам хватит как раз ровно для вычисления определенных функций без всей мощи ООП.
У меня в этом семестре были: политология, социология, БЖД, архитектура ЭВМ, обработка визуальной информации и ничего плохого я в этом не вижу. Пока дают знания - надо брать. А "кодить" можно и в шараге научиться.
Процитирую своего социолога, который на первой лекции сказал очень мудрую вещь.
"Давайте решим, для чего вам все это надо. Вы находитесь в высшем учебном заведении. Вас пичкают разной ерундой. Что вы получите при окончании университета. У вас будет как бы условно два нимба над головой. Один, тот, что поменьше, - это ваши знания в области программирования (специальности), второй нимб побольше говорит о том, что вы инженер и сможете свои знания перенести в любую сторону. Т.е. многосторонне развиты и сможете найти свою нишу в области работы."
Yandex
Объявления
25.01.2013, 02:00     Добавить размеры в код "Обход конем"
Ответ Создать тему
Опции темы

Текущее время: 16:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru