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

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

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

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

C

#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

#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++

#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++

#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++

#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++

#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

int readInteger(const char *message) {
  int result;
  printf("%s: ", message);
  scanf("%d", &result);
  return result;
};

Ну и потом с её помощью проинициализировал все четыре переменные.

C

  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

#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

#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

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

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

@lemegeton 4773 / 2582 / 894 Регистрация: 29.11.2010 Сообщений: 5,590
	24.01.2013, 09:18	29
	Сообщение от UserAK просто я это написал, чтобы показать как заменить шаблонный stack<int> массивом, обойтись без рекурсии и заодно использовать одномерный массив вместо матрицы. вроде получилось, ми доволен Ага, только через код теперь не продраться без пол-банки. ) Еще надо бы от глобальных переменных отказаться. 1

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	25.01.2013, 01:04	35
	Сообщение от lemegeton Чисто из любопытства, на кого вы учитесь, что вам дают такие сложные задачи? У меня во втором семестре было. Рекурсивный и нерекурсивный алгоритмы обхода доски конем + размеры доски задавались с клавиатуры. 0

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

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

@Катерька 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? 0

@lemegeton 4773 / 2582 / 894 Регистрация: 29.11.2010 Сообщений: 5,590
	24.01.2013, 08:45	27
	Сообщение от UserAK lemegeton, посмотрите плиз если не сложно, мой последний код в С будет работать? вроде ничего нет от С++ там? Компилируется, выдает результат. Падает, если нет пути до точки, попробуйте поле размером 3х3. Не по теме: Конечно, решение через стек более универсально, чем через рекурсию, но его сложнее понять. 1

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

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

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

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