Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [C] Лабиринт

Автор: zhuchok 18.11.2006, 07:41

Пожалуйста, укажите мне на мои ошибки и помогите их исправить. И, если можно, помогите усовершенствовать программы. Только чтоб это все работало на C а не на C++. Заранее большое спасибо

"Лабиринт-ввод"

Условия:

Написать программу, позволяющую создавать лабиринты произвольного размера N*M, где M-колличество строк, а N- колличество столбцов. В каждом элементе таблицы находятся либо символ "." либо символ "x". Символ "x" обозначает "непроходимую клетку", тогда как клетки, содержащие точки, - "проходимы". Учитывать ограничения M<25, N<25.
В программе в диалоговом режиме вводятся значения M и N. Далее оператор вводит построчно лаберинт, после ввода последней строки весь лабиринт выводитяся для проверки на экран.
Оператор может исправлять лабиринт, вводя заново одну или несколько строк, в диалоговом режиме программа предлагает узнать номер строки для редактирования, если вводится отрицательное число, программа запрашивает имя выходного файла, выводит для контроля лабиринт на экран и затем лабиринт записывается в указанный файл.

Формат выходного файла:

В первой строке содержится два целых числа N и M, далее следует M строк , содержащих символы "." или "x"

Требования к прграмме:

Программа должна при вводе лабиринта воспринимать только символы "." и "x", остальные просто игнорировать(кроме конца строки). Ввод лабиринта должен быть максимально удобен для оператора.

Код


#include <stdio.h>
#includ <string.h>
#define N10 
char a[N+1];
main()
{
      FILE*f;
      int i,j,jN,c,N;
      f=fopen("lab.txt", "w");
      for (i=0;i<N;i++)
      {
          fgets(a[i],N+1,stdin);
          jN=strlen(a[i])-1;
          while (jN<N) a[i][jN++]='.';
          a[i][N]='\n';
      }
      fprintf(f,"%d %d\n", N,N);
      for (i=0;i<N;i++)
      {
          for(i=0;j<N;j++)
          {
                          if ((a[i][j]!='.')&&(a[i][j]!='x'))
                          a[i][j]='.';
                          fprintf(f,"%c",a[i][j]);
          }
          fprintf(f,"\n");
      }
      fclose(f);
}

"Лабиринт-решение"

Условия:

Написать программу, находящую кратчайший путь в лабиринте от левого верхнего квадрата до нижнего правого. Прграмма должна прочитать из файла лабиринт , созданный при помощи предыдущей программы, сохранить его в двумерном массиве.
Для нахождения рекомендуется использовать "метод волны", заполняя в памяти массив числами, соответствующими пройденому от начального квадрата пути. Вывести найденый путь в лабиринте на экран

Код


#include <stdio.h>
#includ <string.h>
char**a;
main()
{
      FILE*f;
      int i,j,jN,M,N;
      f=fopen("laberint.txt","r");
      fscanf(f,"%d%d@",&M,&N);
      a=malloc(m*sizeof(char**));
      for(i=0,i<M,i++)
      a[i]=malloc(N*sizeof(char));
      for(i=0,i<N,i++)
      {
                      fgets(a[i],N+1,f);
                      strlen(a[i])-1;
                      while (jN<N) a[i][jN++]='.';
                      a[i][N]='\n';
      }
      int level=0;
      a[0][0]=0
      while (a[N-1][N-1]=='.')
      {
            for(i=0,i<N,i++)
            for(j=0,j<N,j++)
            if(a[i][j]==level)
            {
                              if(i-1)>0
                              if((a[i-1][j]!='x')&&(a[i-i][j]>level+1))
                              a[i-1][j]=level+1;
                              if(j-1)>0
                              if((a[j-1][i]!='x')&&(a[j-j][i]>level+1))
                              a[j-1][i]=level+1;
                              if((a[i+1][j]!='x')&&(a[i-i][j]>level+1))
                              a[i+1][j]=level+1;
                              if((a[j+1][i]!='x')&&(a[j-j][i]>level+1))
                              a[j+1][i]=level+1;
            }
      level++;
}

Автор: likehood 19.11.2006, 12:48

Вот решение второй задачи:

Код


#include <stdio.h>    
#include <string.h>    
#include <assert.h>    
#include <conio.h>    

struct Point {    
    int i, j;    
};    
Point *path;    
// массив лабиринта (-1 - стена, 0 - пустая клетка)
int **a;
int nStr, nCol, pathLen = 0;    

void fill(int i, int j, int newLevel)    
{    
    if (i<0 || i>=nStr || j<0 || j>=nCol) return;    
    if (a[i][j] == 0)    
        a[i][j] = newLevel;    
}    

int tryGoBack(int level, int i, int j)    
{    
    if (i<0 || i>=nStr || j<0 || j>=nCol) return 0;    
    if (a[i][j] == level) {    
        path[pathLen].i = i;    
        path[pathLen].j = j;    
        ++pathLen;    
        return 1;    
    }    
    return 0;    
}    

int main(int argc, char *argv[])    
{    
    char *str;    
    int i, j, k, level, nChange;    
    char filename[80] = "laberint.txt";    
    if (argc > 1) // если есть параметры коммандной строки    
        strncpy(filename, argv[1], 80);    // берем имя файла оттуда
    FILE *file = fopen(filename, "rt");    
    if (!file) {
        printf("Can't open file '%s'.\n", filename);
        exit(1);
    }
    fscanf(file, "%d %d", &nStr, &nCol);
    a = (int**) malloc(nStr*sizeof(int*));
    for (i=0; i<nStr; i++)
        a[i] = (int*) malloc(nCol*sizeof(int));
    str = (char*) malloc(nCol*sizeof(char)+2);    
     
    for (i=0; i<nStr; i++)    
    {    
        if (fscanf(file, "%s", str) == NULL) {    
            puts("Error");    
            exit(1);    
        }    
        for (j=0; j<nCol; j++) {    
            if (str[j] == '.') a[i][j] = 0;    
            else a[i][j] = -1;    
        }    
    }    
    fclose(file);    
    free(str);    
    if (a[nStr-1][nCol-1] == -1 || a[0][0]==-1) {    
        puts("Error: right bottom or top left element is not free.");    
        exit(1);    
    }    
    a[0][0] = 1;    
    level = 1;    
    do {
        // количество клеток с текущим уровнем
        nChange = 0;    
        for (i=0; i<nStr; i++)    
            for (j=0; j<nCol; j++)    
            {    
                if (a[i][j] == level) {
                    // пытаемся заполнить соседние ячейки (если они пусты)
                    fill(i-1, j, level+1);    
                    fill(i+1, j, level+1);    
                    fill(i, j-1, level+1);    
                    fill(i, j+1, level+1);    
                    nChange++;
                }    
            }    
            ++level;    
    } 
    // если nChange==0, то волна "уперлась" в стенки, не дойдя до выхода из лабиринта
    while (nChange > 0 && a[nStr-1][nCol-1] == 0);
    if (a[nStr-1][nCol-1] == 0) {    
        puts("There is no path from left top corner to right bottom one.");    
        getch(); exit(1);    
    }    
         
    // эту проверку можно убрать - нужна только для отладки
    assert(level == a[nStr-1][nCol-1]);
    // в path будут заноститься точки пути от конца к началу лабиринта
    path = (Point*) malloc(level*sizeof(Point));    
    i = nStr-1; j = nCol-1;    // стартуем с конца пути
    path[pathLen].i = nStr-1;
    path[pathLen].j = nCol-1;
    ++pathLen;
    for (; level>1; level--)    
    {    
        int ii=i, jj=j;    
        // функция tryGoBack проверяет, является ли точка чатью пути
        // с уровнем на 1 меньшем текущего.
        // если да, то точка заноситься в массив path, сама точка становиться
        // такущей и мы идем к следующему шагу цикла.
        if (tryGoBack(level-1, i=ii-1, jj)) continue;    
        if (tryGoBack(level-1, i=ii+1, jj)) continue;    
        if (tryGoBack(level-1, i=ii, j=jj-1)) continue;    
        if (tryGoBack(level-1, ii, j=jj+1)) continue;    
    }    
    assert(pathLen==a[nStr-1][nCol-1]);    // нужно для отладки
    // дальше рисуем рамку вокруг лабиринта и сам лабиринт
    putchar(0xDA);    
    for (j=0; j<2*nCol; j++)    
        putchar('-');    
    puts("\xBF");    
    for (i=0; i<nStr; i++)    
    {    
        putchar('|');    
        for (j=0; j<nCol; j++)    
        {    
            // смотрим, входит ли текущая точка в путь
            for (k=0; k<pathLen; k++)    
                if (path[k].i==i && path[k].j==j) {    
                    // если да, то отобрадаем ее в виде точки
                    putchar('.');    
                    break;    
                }
            // если не входит
            if (k==pathLen)    
            {    
                if (a[i][j] == -1)    
                    putchar('x');    
                else putchar(' ');    
            }    
            putchar(' ');    
        }    
        puts("|");    
    }    
    // рисуем нижнюю часть рамки
    putchar(0xC0);    
    for (j=0; j<2*nCol; j++)    
        putchar('-');    
    puts("\xD9");
    // чистим память
    for (i=0; i<nStr; i++)    
        free(a[i]);    
    free(a);    
    free(path);    
    getch();    
    return 0;    
}

Что касается ввода лабиринта, то имхо проще непосредственно редактировать файл в любом текстовом редакторе.
Тогда если надо исправить только одну клетку, не придется заново вводить всю строку.

Автор: zhuchok 19.11.2006, 13:42

baronp, Спасибо большое. Если б это от меня зависело smile

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

Автор: likehood 19.11.2006, 17:50

добавил в предыдущий пост немного комментариев. Будут вопросы - пиши.

Автор: zhuchok 22.11.2006, 11:58

baronp, у меня компилятор очень структурой Point недоволен а я не могу разобраться что ему не нравится

Автор: likehood 22.11.2006, 23:29

Точно, в Си перед именем структуры надо писать слово struct. Вот исправленный код:

Код


#include <stdio.h>     
#include <string.h>     
#include <assert.h>     
#include <conio.h>     
typedef struct Point {     
    int i, j;     
} Point;     
struct Point *path;     
// массив лабиринта (-1 - стена, 0 - пустая клетка)    
int **a;    
int nStr, nCol, pathLen = 0;     
void fill(int i, int j, int newLevel)     
{     
    if (i<0 || i>=nStr || j<0 || j>=nCol) return;     
    if (a[i][j] == 0)     
        a[i][j] = newLevel;     
}     
int tryGoBack(int level, int i, int j)     
{     
    if (i<0 || i>=nStr || j<0 || j>=nCol) return 0;     
    if (a[i][j] == level) {     
        path[pathLen].i = i;     
        path[pathLen].j = j;     
        ++pathLen;     
        return 1;     
    }     
    return 0;     
}     
int main(int argc, char *argv[])     
{     
    char *str;     
    int i, j, k, level, nChange;     
    char filename[80] = "laberint.txt";     
    if (argc > 1) // если есть параметры коммандной строки     
        strncpy(filename, argv[1], 80);    // берем имя файла оттуда    
    FILE *file = fopen(filename, "rt");     
    if (!file) {    
        printf("Can't open file '%s'.\n", filename);    
        exit(1);    
    }    
    fscanf(file, "%d %d", &nStr, &nCol);    
    a = (int**) malloc(nStr*sizeof(int*));    
    for (i=0; i<nStr; i++)    
        a[i] = (int*) malloc(nCol*sizeof(int));    
    str = (char*) malloc(nCol*sizeof(char)+2);     
      
    for (i=0; i<nStr; i++)     
    {     
        if (fscanf(file, "%s", str) == NULL) {     
            puts("Error");     
            exit(1);     
        }     
        for (j=0; j<nCol; j++) {     
            if (str[j] == '.') a[i][j] = 0;     
            else a[i][j] = -1;     
        }     
    }     
    fclose(file);     
    free(str);     
    if (a[nStr-1][nCol-1] == -1 || a[0][0]==-1) {     
        puts("Error: right bottom or top left element is not free.");     
        exit(1);     
    }     
    a[0][0] = 1;     
    level = 1;     
    do {    
        // количество клеток с текущим уровнем    
        nChange = 0;     
        for (i=0; i<nStr; i++)     
            for (j=0; j<nCol; j++)     
            {     
                if (a[i][j] == level) {    
                    // пытаемся заполнить соседние ячейки (если они пусты)    
                    fill(i-1, j, level+1);     
                    fill(i+1, j, level+1);     
                    fill(i, j-1, level+1);     
                    fill(i, j+1, level+1);     
                    nChange++;    
                }     
            }     
            ++level;     
    }    
    // если nChange==0, то волна "уперлась" в стенки, не дойдя до выхода из лабиринта    
    while (nChange > 0 && a[nStr-1][nCol-1] == 0);    
    if (a[nStr-1][nCol-1] == 0) {     
        puts("There is no path from left top corner to right bottom one.");     
        getch(); exit(1);     
    }     
          
    // эту проверку можно убрать - нужна только для отладки    
    assert(level == a[nStr-1][nCol-1]);    
    // в path будут заноститься точки пути от конца к началу лабиринта    
    path = (struct Point*) malloc(level*sizeof(struct Point));     
    i = nStr-1; j = nCol-1;    // стартуем с конца пути    
    path[pathLen].i = nStr-1;    
    path[pathLen].j = nCol-1;    
    ++pathLen;    
    for (; level>1; level--)     
    {     
        int ii=i, jj=j;     
        // функция tryGoBack проверяет, является ли точка чатью пути    
        // с уровнем на 1 меньшем текущего.    
        // если да, то точка заноситься в массив path, сама точка становиться    
        // такущей и мы идем к следующему шагу цикла.    
        if (tryGoBack(level-1, i=ii-1, jj)) continue;     
        if (tryGoBack(level-1, i=ii+1, jj)) continue;     
        if (tryGoBack(level-1, i=ii, j=jj-1)) continue;     
        if (tryGoBack(level-1, ii, j=jj+1)) continue;     
    }     
    assert(pathLen==a[nStr-1][nCol-1]);    // нужно для отладки    
    // дальше рисуем рамку вокруг лабиринта и сам лабиринт    
    putchar(0xDA);     
    for (j=0; j<2*nCol; j++)     
        putchar('-');     
    puts("\xBF");     
    for (i=0; i<nStr; i++)     
    {     
        putchar('|');     
        for (j=0; j<nCol; j++)     
        {     
            // смотрим, входит ли текущая точка в путь    
            for (k=0; k<pathLen; k++)     
                if (path[k].i==i && path[k].j==j) {     
                    // если да, то отобрадаем ее в виде точки    
                    putchar('.');     
                    break;     
                }    
            // если не входит    
            if (k==pathLen)     
            {     
                if (a[i][j] == -1)     
                    putchar('x');     
                else putchar(' ');     
            }     
            putchar(' ');     
        }     
        puts("|");     
    }     
    // рисуем нижнюю часть рамки    
    putchar(0xC0);     
    for (j=0; j<2*nCol; j++)     
        putchar('-');     
    puts("\xD9");    
    // чистим память    
    for (i=0; i<nStr; i++)     
        free(a[i]);     
    free(a);     
    free(path);     
    getch();     
    return 0;     
}

Автор: zhuchok 23.11.2006, 11:38

baronp, ещё в строке 49 ругается на сравнение между указателем и целым числом

Автор: likehood 23.11.2006, 14:08

можешь вообще этот if убрать, я его сделал для отладки а потом забыл убрать.
то есть надо оставить только fscanf:

Код


fscanf(file, "%s", str);

вместо

Код


        if (fscanf(file, "%s", str) == NULL) {      
            puts("Error");      
            exit(1);      
        }

Автор: zhuchok 26.11.2006, 04:48

baronp, пасибо огомное. А с первой прогой не поможешь smile

хотябы мою отредактировать чтоб она работала smile

Автор: cardinal 26.11.2006, 15:52

Цитата(zhuchok @ 26.11.2006, 02:48

)

хотябы мою отредактировать чтоб она работала

А отладчик зачем? Это очень важно научиться понимать, что он тебе говорит...

Автор: likehood 26.11.2006, 19:32

вот решение первой задачи:

Код


#include <malloc.h>
#include <conio.h>
#include <stdio.h>

char **a;
int nStr, nCol;

void enterLine(int i)
{
    int j, ch;
    for (j=0; j<nCol; j++)
    {
        do {
            ch = getch();
        } while (ch != 'x' && ch != '.');
        a[i][j] = ch;
        putchar(ch);
    }
    while ( (ch=getch()) != '\r');
    putchar('\n');
}

void printMatrix()
{
    int i, j;
    for (i=0; i<nStr; i++)
    {
        for (j=0; j<nCol; j++)
            putchar(a[i][j]);
        putchar('\n');
    }
}

void printDelim()
{
    int j;
    for (j=0; j<nCol; j++)
        putchar('-');
    putchar('\n');
}

int main()
{
    int i, j;
    char fileName[80];
    FILE *file;
    printf("Enter number of lines: ");
    scanf("%d", &nStr);
    printf("Enter number of columns: ");
    scanf("%d", &nCol);
    a = (char**) malloc(nStr*sizeof(char*));    
    for (i=0; i<nStr; i++)    
        a[i] = (char*) malloc(nCol*sizeof(char));    
    for (i=0; i<nStr; i++)
        enterLine(i);

    printDelim();
    printMatrix();
    printDelim();

    do {
        printf("Enter the number of line to correct: ");
        scanf("%d", &i);
        if (1 <= i && i <= nCol) enterLine(i-1);
    } while (i >= 0);
    
    printDelim();
    printMatrix();
    printDelim();

    printf("Enter the name of file to store labyrinth in: ");
    scanf("%s", fileName);
    file = fopen(fileName, "w");
    if (!file) {
        fprintf(stderr, "Can't open file '%s'.\n", fileName);
        return 1;
    }
    fprintf(file, "%d %d\n", nStr, nCol);
    for (i=0; i<nStr; i++) {
        for (j=0; j<nCol; j++)
            putc(a[i][j], file);
        putc('\n', file);
    }
    fclose(file);

    for (i=0; i<nStr; i++)     
        free(a[i]);     
    free(a);     
    return 0;
}

Автор: zhuchok 27.11.2006, 11:30

baronp, grand merci. Очень здорово помог.

cardinal, Дак вот жее... усадили девушку за комп сказали "учи!" smile

Автор: likehood 27.11.2006, 14:23

Цитата(zhuchok @ 27.11.2006, 12:30

)

cardinal, Дак вот жее... усадили девушку за комп сказали "учи!"

Ну так и учись! Читай книги, пиши программы, смотри как пишут другие. Если ты действительно хочешь учиться, то без этого никак. В тех прогах, что ты сама написала, конечно, хватает ошибок, но все же там чувствуется движение мысли в правильном направлении, чего не хватает многим новичкам.

Автор: zhuchok 27.11.2006, 15:59

baronp, эх... учусь... не плохо бы ещё учителя хорошего... по книгам сложновато smile