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

@Катерька · Регистрация: 07.01.2013

Студворк — интернет-сервис помощи студентам

Господа,решила в новой теме попросить помощи.есть код

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 · 23.01.2013, 23:56

Я тут вот чего придумал. Поскольку исходная точка одна, задача сводится к помеси алгоритма Дейкстры с волновым алгоритмом. Надо просто заполнить все возможные минимальные варианты хода коня по всем возможным клеткам, начиная с исходной. Т.е. не надо ни сложных матриц смежности, ни структур типа стек.

Простейшая реализация через рекурсию.

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 · 24.01.2013, 02:24

вот вариант с одномерным массивом

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 минуты

@Катерька · 24.01.2013, 03:19 **[ТС]**

lemegeton, вы чудесны,код просто идеально подходит))
он все не отстанет с загрузкой размеров и координатов..можно ли с помощью printf использовать height,wigth,координаты y и x для загрузки?

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

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

Добавлено через 12 минут
..эээ..через printf понятно,как это сделать,а тут..или совместно с printf делать и scanf,чтобы он просил вводить данные?уфф..помогите последний раз,я отвяжусь,любезный
lemegeton?

@UserAK · 24.01.2013, 08: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 · 24.01.2013, 08: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 · 24.01.2013, 08:28

ну вот вроде ничего от C++ не осталось

Добавлено через 1 минуту
lemegeton, посмотрите плиз если не сложно, мой последний код в С будет работать? вроде ничего нет от С++ там?

@lemegeton · 24.01.2013, 08:45

Сообщение от UserAK

lemegeton, посмотрите плиз если не сложно, мой последний код в С будет работать? вроде ничего нет от С++ там?

Компилируется, выдает результат.
Падает, если нет пути до точки, попробуйте поле размером 3х3.

Не по теме:

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

@UserAK · 24.01.2013, 09:12

вот теперь не падает и пишет если нет пути, спасибо )

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 · 24.01.2013, 09:18

Сообщение от UserAK

просто я это написал, чтобы показать как заменить шаблонный stack<int> массивом, обойтись без рекурсии и заодно использовать одномерный массив вместо матрицы. вроде получилось, ми доволен

Ага, только через код теперь не продраться без пол-банки. )
Еще надо бы от глобальных переменных отказаться.

@UserAK · 24.01.2013, 09:31

что верно, то верно
это всё ради того, что бы было как можно меньше параметров всяких у функций

вот даже макросов налепил

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

Добавлено через 2 минуты
и решил не таскать туда-сюда эту несчастную матрицу из функции в функцию, сделал глобальной, да и всё остальное заодно уж

@Катерька · 24.01.2013, 18:00 **[ТС]**

Сообщение от lemegeton

Да, конечно. Переменные height, width, x и y вполне можно считывать с консоли вместо инициализации константами. Все будет работать.

Вот пример ввода. Сделайте по аналогии.
Обратите внимание на амперсанд перед width в scanf'е. Он очень важен.

C
1
2
3
  int width;
  printf("Enter width: ");
  scanf("%d", &width);

я так у себя и сделала,только вот значений потребовалось вводить больше,чем мне показалось нужным.value ведь тоже нужно инициализировать?

Добавлено через 2 минуты
а каждый раз int писать по идее не нужно,ведь есть строка,которая относит все величины к типу int

@lemegeton · 24.01.2013, 19:27

Сообщение от Катерька

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");;

И все, никого больше никуда вводить не надо.

@Катерька · 25.01.2013, 00:19 **[ТС]**

Премногоуважаемый 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 · 25.01.2013, 00:52

Ыыы... Оно компилируется.

Сообщение от Катерька

сказал,что так это не работает.что я делаю не так?

Много всего. Я, пожалуй, не стану даже пытаться объяснить.

Сообщение от Катерька

код вставила Ваш..чтобы инициализировал переменные с помощью 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 · 25.01.2013, 01:04

Сообщение от lemegeton

Чисто из любопытства, на кого вы учитесь, что вам дают такие сложные задачи?

У меня во втором семестре было. Рекурсивный и нерекурсивный алгоритмы обхода доски конем + размеры доски задавались с клавиатуры.

@небритый еж · 25.01.2013, 01:12

lemegeton, не поверите,специальность совсем не связана с программированием,но предмет обязательный.мало того,еще в следующем семестре будет С++.Так что готовьтесь,я скоро буду )))
факультет ядерной физики,специальность связана с радиацией.лол,да?казалось бы,к чему оно нужно.

@Катерька · 25.01.2013, 01:16 **[ТС]**

прошу прощения,не вышла из аккаунта,сосед по комнате тоже на форуме этом сидит,свою задачку ищет))общажные дела.

MrGluck · 25.01.2013, 01:16

небритый еж, затем же, зачем и программистам ядерная или квантовая физика.
Чтоб было общее развитие и мы были друг с другом на одной волне

@Катерька · 25.01.2013, 01:22 **[ТС]**

MrGluck, это мой пост,я пометила,что с чужого аккаунта просто написала))
ну знаете..с компьютером я разбираюсь отлично,но этого недостаточно видимо.мало того,что был на прошлом курсе паскаль,так еще в этом году всунули С и С++. То есть приеду я куда-нибудь с проверкой замерять загрязненность почвы,а если работы мало окажется,то где-то на дому смогу программку написать требующим..за небольшую плату.так чтоле.Мне физика гораздо интереснее.А программирование я просто уважаю.я с ним на Вы.

MrGluck · 25.01.2013, 02:00

Катерька, захотите програмку какую-нибудь написать для подсчета своего маленького коллайдера - запрограммируете, знаний вам хватит как раз ровно для вычисления определенных функций без всей мощи ООП.
У меня в этом семестре были: политология, социология, БЖД, архитектура ЭВМ, обработка визуальной информации и ничего плохого я в этом не вижу. Пока дают знания - надо брать. А "кодить" можно и в шараге научиться.
Процитирую своего социолога, который на первой лекции сказал очень мудрую вещь.
"Давайте решим, для чего вам все это надо. Вы находитесь в высшем учебном заведении. Вас пичкают разной ерундой. Что вы получите при окончании университета. У вас будет как бы условно два нимба над головой. Один, тот, что поменьше, - это ваши знания в области программирования (специальности), второй нимб побольше говорит о том, что вы инженер и сможете свои знания перенести в любую сторону. Т.е. многосторонне развиты и сможете найти свою нишу в области работы."

Новые блоги и статьи Все статьи Все блоги /
Remote Connection Manager DevAlt 21.06.2026 Написал для себя небольшую прилагу: https:/ / github. com/ altbodhi/ ReConMan По итогу пришел к мысли, что DU не дружат с существующими технологиями. От сериализации до отображения в реляционную. . .	Администрация Хабра удаляет новые энрегоэфективные алгоритмы, которые не западной школы кода, и вовсе никак не сгенерировавны. Hrethgir 20.06.2026 Делается это, как замечено, при правках - при объявлении концептуальных отличий в алгоримах. Делается это, по линейке событий - после дополнения публикации основными отличиями от основных западных. . .	Процесс ориентированная диалектика (не новость - просто системное обновление, философия). Hrethgir 20.06.2026 Однажды один участник в своём блоге, на этом форуме, сделал запись "О языках замолвите слово". Понимая, что язык - важная вещь, я решил хорошо подумать, прежде чем сказать, и сказал то, что вы видите. . .	Контроль уникальности строк в табличной части документа Maks 18.06.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ПланированиеСпецтехники" с табличной частью "НаличиеОборудования", разработанного в КА2. Задача: контроль уникальности строк в. . .
Клиент Uhbif79 18.06.2026 Здесь простой клиент для работы с сервером.	Сервер Uhbif79 18.06.2026 Выкладываю простейший сервер.	Дефенестрация kumehtar 18.06.2026 Узнал интересное слово. Дефенестрация. Это когда ты выбрасываешь кого-либо или что-либо из окна. Возьму на вооружение)))	Дихотомия добра и зла kumehtar 18.06.2026 Как Дзен-буддисты говорят о добре и зле: не нужно воевать против зла, нужно воевать против невежества. Тогда добро станет ествественным, и поэтому вечным. Но дело в том, что невежество всё время. . .

@Катерька 0 / 0 / 0 Регистрация: 07.01.2013 Сообщений: 32
	24.01.2013, 03:19 [ТС]
	lemegeton, вы чудесны,код просто идеально подходит)) он все не отстанет с загрузкой размеров и координатов..можно ли с помощью printf использовать height,wigth,координаты y и x для загрузки? Добавлено через 44 секунды UserAK, спасибо и Вам,к сожалению,препод поставил строгий запрет на С++... Добавлено через 15 минут попросил загрузить с помощью scanf Добавлено через 12 минут ..эээ..через printf понятно,как это сделать,а тут..или совместно с printf делать и scanf,чтобы он просил вводить данные?уфф..помогите последний раз,я отвяжусь,любезный lemegeton? 0

@UserAK 73 / 73 / 13 Регистрация: 25.12.2012 Сообщений: 189 Записей в блоге: 2
	24.01.2013, 08:28
	ну вот вроде ничего от C++ не осталось Добавлено через 1 минуту lemegeton, посмотрите плиз если не сложно, мой последний код в С будет работать? вроде ничего нет от С++ там? 0

@UserAK 73 / 73 / 13 Регистрация: 25.12.2012 Сообщений: 189 Записей в блоге: 2
	24.01.2013, 09:31
	что верно, то верно это всё ради того, что бы было как можно меньше параметров всяких у функций вот даже макросов налепил Добавлено через 2 минуты сначала сделал с рекурсией, но ввёл что-то вроде 100х100 и стэк лопнул. тогда вот и решил извратиться Добавлено через 2 минуты и решил не таскать туда-сюда эту несчастную матрицу из функции в функцию, сделал глобальной, да и всё остальное заодно уж 0

@небритый еж 0 / 0 / 0 Регистрация: 24.01.2013 Сообщений: 49
	25.01.2013, 01:12
	lemegeton, не поверите,специальность совсем не связана с программированием,но предмет обязательный.мало того,еще в следующем семестре будет С++.Так что готовьтесь,я скоро буду ))) факультет ядерной физики,специальность связана с радиацией.лол,да?казалось бы,к чему оно нужно. 0

@Катерька 0 / 0 / 0 Регистрация: 07.01.2013 Сообщений: 32
	25.01.2013, 01:16 [ТС]
	прошу прощения,не вышла из аккаунта,сосед по комнате тоже на форуме этом сидит,свою задачку ищет))общажные дела. 0

MrGluck Форумчанин 8216 / 5047 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	25.01.2013, 01:16
	небритый еж, затем же, зачем и программистам ядерная или квантовая физика. Чтоб было общее развитие и мы были друг с другом на одной волне 0

@Катерька 0 / 0 / 0 Регистрация: 07.01.2013 Сообщений: 32
	25.01.2013, 01:22 [ТС]
	MrGluck, это мой пост,я пометила,что с чужого аккаунта просто написала)) ну знаете..с компьютером я разбираюсь отлично,но этого недостаточно видимо.мало того,что был на прошлом курсе паскаль,так еще в этом году всунули С и С++. То есть приеду я куда-нибудь с проверкой замерять загрязненность почвы,а если работы мало окажется,то где-то на дому смогу программку написать требующим..за небольшую плату.так чтоле.Мне физика гораздо интереснее.А программирование я просто уважаю.я с ним на Вы. 0

MrGluck Форумчанин 8216 / 5047 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	25.01.2013, 02:00
	Катерька, захотите програмку какую-нибудь написать для подсчета своего маленького коллайдера - запрограммируете, знаний вам хватит как раз ровно для вычисления определенных функций без всей мощи ООП. У меня в этом семестре были: политология, социология, БЖД, архитектура ЭВМ, обработка визуальной информации и ничего плохого я в этом не вижу. Пока дают знания - надо брать. А "кодить" можно и в шараге научиться. Процитирую своего социолога, который на первой лекции сказал очень мудрую вещь. "Давайте решим, для чего вам все это надо. Вы находитесь в высшем учебном заведении. Вас пичкают разной ерундой. Что вы получите при окончании университета. У вас будет как бы условно два нимба над головой. Один, тот, что поменьше, - это ваши знания в области программирования (специальности), второй нимб побольше говорит о том, что вы инженер и сможете свои знания перенести в любую сторону. Т.е. многосторонне развиты и сможете найти свою нишу в области работы." 0