Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
#1

Обход матрицы по 0 с заданного элемента - C++

23.04.2013, 11:18. Просмотров 860. Ответов 26
Метки нет (Все метки)

Дана квадратная матрица, состоящая из 0 и 1...делается обход начинаю с какого то элемента... пробегается по 0, например вправо, если встречается 1, то мы меняем маршрут, вниз или вверх, если опять встречается 1, то опять меняем маршрут.....требуется написать программу, которая напишет номер элемента, который сможет пройтись таким образом по всем нулям....реализовать поиск с помощью рекурсивной функции...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.04.2013, 11:18
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Обход матрицы по 0 с заданного элемента (C++):

Функция нахождения минимального элемента заданного столбца матрицы - C++
Написать библиотеку функций для работы с квадратной целочисленной матрицей а)Функция для инициализации массива случайными числами из...

Вставка элемента в заданную позицию, удаление элемента по заданной позиции, поиск заданного элемента - C++
Добавить в класс "Односвязный список" следующие функции: вставка элемента в заданную позицию, удаление элемента по заданной позиции, поиск...

В пользовательском классе List (список) реализовать вставку элемента после заданного элемента - C++
Помогите пожалуйста, мне надо сделать вставку элемента после найденного, а у меня элемент добавляется на место первого элемента. ...

Поиск элемента с заданным ключом в бинарном дереве, используя обход - C++
Помогите пожалуйста! Необходимо найти элемент с заданным ключом в бинарном дереве, используя обход дерева снизу вверх (обратный обход).

Обход матрицы - C++
есть двумерная матрица 4х4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 ее рандомно перемешиваем. потом берем...

Обход матрицы - C++
Нужно составить программу ввода квадратной матрицы и печати в строку всех ее элементов в данном порядке обхода: 7 13 14 16 6 8 12 15 ...

26
Wladius
12 / 7 / 2
Регистрация: 06.01.2013
Сообщений: 127
23.04.2013, 11:21 #2
А как она сможет пройтись по всем 0 в таком случае?

1 1 1 1 0 0 0
1 0 0 1 0 0 0
1 0 0 1 0 0 0
1 1 1 1 0 0 0
0
chizz
981 / 496 / 54
Регистрация: 19.03.2013
Сообщений: 3,095
Записей в блоге: 18
Завершенные тесты: 1
23.04.2013, 11:23 #3
а еще в несколько потоков, чтобы сразу N ячеек проверять

Добавлено через 32 секунды
Цитата Сообщение от Wladius Посмотреть сообщение
А как она сможет пройтись по всем 0 в таком случае?
Никак. В этом случае пишем, что нет таких
0
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
23.04.2013, 11:48  [ТС] #4
вот дали такую задачу=) сказали мегопростая=) я убедился в обратном=)

Добавлено через 1 минуту
Цитата Сообщение от Wladius Посмотреть сообщение
А как она сможет пройтись по всем 0 в таком случае?

1 1 1 1 0 0 0
1 0 0 1 0 0 0
1 0 0 1 0 0 0
1 1 1 1 0 0 0
я плюс ко всему сказал что матрица квадратная) ну и если не сможет то выдать что такого маршрута нет) и кстати надо записать маршрут) напримеер 1-вправо, 2-влево, 3-вниз, 4-вверх
0
chizz
981 / 496 / 54
Регистрация: 19.03.2013
Сообщений: 3,095
Записей в блоге: 18
Завершенные тесты: 1
23.04.2013, 14:39 #5
Ну вот например. Только надо еще запоминать, где мы проходили, а где нет. А то так закикливается, по кругу бегает.

Если убрать if (cnt>6) return path; то в бесконечный цикл уйдет.

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
#include <cstdlib>
#include <iostream>
 
using namespace std;
static string path;
 
 
int M[3][3] = {{0,1,0}, {0,0,1}, {0,0,1}};
 
 
static std::string getpath(string path, int j, int i, string last, int cnt) {
     string tmppath;   
     
   if (cnt>6) return path;    
    
    if (last!="left")      
    if (j+1==3) ;
       else if (M[j+1][i] == 1) ;
        else getpath(path+" right",j+1,i,"right",cnt+1);
       
    if (last!="right")       
    if (j-1==-1) ;
       else if (M[j-1][i] == 1) ;
        else getpath(path+" left",j-1,i,"left",cnt+1);
        
    if (last!="down")       
    if (i-1==-1) ;
       else if (M[j][i-1] == 1) ;
        else getpath(path+" up",j,i-1,"up",cnt+1);  
        
    if (last!="up")       
    if (i+1==3) ;
       else if (M[j][i+1] == 1) ;
        else getpath(path+" down",j,i+1,"down",cnt+1);          
         
         
         if (path!="Element:")
         cout << path  << endl; 
        
         return path;
       
       }
 
int main(int argc, char *argv[])
{  
 
//ji
 
for (int i=0;i<3;i++)
{
 cout << endl;
 for (int j=0; j<3; j++)
  cout << M[j][i] ;
}
  
   cout << endl;
  
for (int i=0;i<3;i++)
 for (int j=0; j<3; j++)
  {
        path+="Element:"; 
        cout<<j<<" "<<i<<endl;
        getpath(path, j,i,"first",0);
      
    
        //  cout<< path << endl;
          path = ""; 
                  
          }
                 
    system("PAUSE");
    return EXIT_SUCCESS;
}
Я еще алгоритм перед этим писал, только реализация может отличаться)

Кликните здесь для просмотра всего текста
2. проход по всем ячейкам

for (i=0;i<m;i++)
for (j=0;j<m;j++)
запуск проверки ячейки

Процедура проверки ячейки.

ячейка a[i][j]

в путь пишем ячейка i j

- проход вправо
- влево
- вверх
- вниз.

проход вправо.

if (i+1=m) выход (достигли стенки справа)
else if (a[i+1][j] = 1) выход (вправо нельзя, там единица).
else
записываем путь и вызываем проверку ячейки a[i+1][j]

проход влево

if (i-1=-1) выход (достигли стенки слева)
else if (a[i-1][j] = 1) выход (влево нельзя, там единица).
else
записываем путь и вызываем проверку ячейки a[i-1][j]

проход вверх

if (j+1=m) выход (достигли стенки сверху)
else if (a[i][j+1] = 1) выход (вверх нельзя, там единица)
else
записываем путь и вызываем проверку ячейки a[i][j+1]


проход Вниз

if (j-1=m) выход (достигли стенки сверху)
else if (a[i][j-1] = 1) выход (вниз нельзя, там единица)
else
записываем путь и вызываем проверку ячейки a[i][j-1]

тут возвращаем путь и обнуляем его.
0
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
23.04.2013, 16:39  [ТС] #6
Цитата Сообщение от chizz Посмотреть сообщение
Ну вот например. Только надо еще запоминать, где мы проходили, а где нет. А то так закикливается, по кругу бегает.

Если убрать if (cnt>6) return path; то в бесконечный цикл уйдет.

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
#include <cstdlib>
#include <iostream>
 
using namespace std;
static string path;
 
 
int M[3][3] = {{0,1,0}, {0,0,1}, {0,0,1}};
 
 
static std::string getpath(string path, int j, int i, string last, int cnt) {
     string tmppath;   
     
   if (cnt>6) return path;    
    
    if (last!="left")      
    if (j+1==3) ;
       else if (M[j+1][i] == 1) ;
        else getpath(path+" right",j+1,i,"right",cnt+1);
       
    if (last!="right")       
    if (j-1==-1) ;
       else if (M[j-1][i] == 1) ;
        else getpath(path+" left",j-1,i,"left",cnt+1);
        
    if (last!="down")       
    if (i-1==-1) ;
       else if (M[j][i-1] == 1) ;
        else getpath(path+" up",j,i-1,"up",cnt+1);  
        
    if (last!="up")       
    if (i+1==3) ;
       else if (M[j][i+1] == 1) ;
        else getpath(path+" down",j,i+1,"down",cnt+1);          
         
         
         if (path!="Element:")
         cout << path  << endl; 
        
         return path;
       
       }
 
int main(int argc, char *argv[])
{  
 
//ji
 
for (int i=0;i<3;i++)
{
 cout << endl;
 for (int j=0; j<3; j++)
  cout << M[j][i] ;
}
  
   cout << endl;
  
for (int i=0;i<3;i++)
 for (int j=0; j<3; j++)
  {
        path+="Element:"; 
        cout<<j<<" "<<i<<endl;
        getpath(path, j,i,"first",0);
      
    
        //  cout<< path << endl;
          path = ""; 
                  
          }
                 
    system("PAUSE");
    return EXIT_SUCCESS;
}
Я еще алгоритм перед этим писал, только реализация может отличаться)

Кликните здесь для просмотра всего текста
2. проход по всем ячейкам

for (i=0;i<m;i++)
for (j=0;j<m;j++)
запуск проверки ячейки

Процедура проверки ячейки.

ячейка a[i][j]

в путь пишем ячейка i j

- проход вправо
- влево
- вверх
- вниз.

проход вправо.

if (i+1=m) выход (достигли стенки справа)
else if (a[i+1][j] = 1) выход (вправо нельзя, там единица).
else
записываем путь и вызываем проверку ячейки a[i+1][j]

проход влево

if (i-1=-1) выход (достигли стенки слева)
else if (a[i-1][j] = 1) выход (влево нельзя, там единица).
else
записываем путь и вызываем проверку ячейки a[i-1][j]

проход вверх

if (j+1=m) выход (достигли стенки сверху)
else if (a[i][j+1] = 1) выход (вверх нельзя, там единица)
else
записываем путь и вызываем проверку ячейки a[i][j+1]


проход Вниз

if (j-1=m) выход (достигли стенки сверху)
else if (a[i][j-1] = 1) выход (вниз нельзя, там единица)
else
записываем путь и вызываем проверку ячейки a[i][j-1]

тут возвращаем путь и обнуляем его.

эм, а вместо string char нельзя?

Добавлено через 3 минуты
и она не хочет компилиться(
0
chizz
981 / 496 / 54
Регистрация: 19.03.2013
Сообщений: 3,095
Записей в блоге: 18
Завершенные тесты: 1
23.04.2013, 16:41 #7
Цитата Сообщение от Lonter Посмотреть сообщение
эм, а вместо string char нельзя?
Ну если для вас трудно вместо string сделать char, тогда эта задача для вас действительно не простая

ТОгда вам надо тему было открыть в разделе C для начинающих, а не C++
0
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
23.04.2013, 16:43  [ТС] #8
ну меня чисто интересовало, изменится ли что-то от этого)

Добавлено через 1 минуту
у меня именно с++, ну я фактически понимаю что это))
0
chizz
981 / 496 / 54
Регистрация: 19.03.2013
Сообщений: 3,095
Записей в блоге: 18
Завершенные тесты: 1
23.04.2013, 16:46 #9
Цитата Сообщение от Lonter Посмотреть сообщение
изменится ли что-то от этого
Способы ввода-вывода, объявления и передачи в функции. Больше ничего

Добавлено через 1 минуту
Цитата Сообщение от Lonter Посмотреть сообщение
у меня именно с++
Я писал это в Bloodshed Dev C++
Наверное в вашем IDE свои особенности.

Создайте пустой проект и вставьте туда содержимое main и функцию getpath. Может скомпилится.
0
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
23.04.2013, 16:49  [ТС] #10
у меня VS2010 C++

Добавлено через 2 минуты
самая главная ошибка это преобразования const char в char и const char в int, где !=
0
chizz
981 / 496 / 54
Регистрация: 19.03.2013
Сообщений: 3,095
Записей в блоге: 18
Завершенные тесты: 1
23.04.2013, 16:51 #11
Уберите system("PAUSE");
и return EXIT_SUCCESS;

после чего напишите, на что ругается
0
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
23.04.2013, 16:53  [ТС] #12
ничего не изменилось=(
0
chizz
981 / 496 / 54
Регистрация: 19.03.2013
Сообщений: 3,095
Записей в блоге: 18
Завершенные тесты: 1
23.04.2013, 16:55 #13
Цитата Сообщение от Lonter Посмотреть сообщение
ничего не изменилось=(
Код в студию. + ошибки компиляции
0
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
23.04.2013, 16:57  [ТС] #14
#include <cstdlib>
#include <iostream>

using namespace std;
static string path;


int M[3][3] = {{0,1,0}, {0,0,1}, {0,0,1}};


char getpath(char path, int j, int i, char last, int cnt) {


if (cnt>6) return path;

if (last!="left")
if (j+1==3) ;
else if (M[j+1][i] == 1) ;
else getpath(path+" right",j+1,i,"right",cnt+1);

if (last!="right")
if (j-1==-1) ;
else if (M[j-1][i] == 1) ;
else getpath(path+" left",j-1,i,"left",cnt+1);

if (last!="down")
if (i-1==-1) ;
else if (M[j][i-1] == 1) ;
else getpath(path+" up",j,i-1,"up",cnt+1);

if (last!="up")
if (i+1==3) ;
else if (M[j][i+1] == 1) ;
else getpath(path+" down",j,i+1,"down",cnt+1);


if (path!="Element:")
cout << path << endl;

return path;

}

int main(int argc, char *argv[])
{



for (int i=0;i<3;i++)
{
cout << endl;
for (int j=0; j<3; j++)
cout << M[j][i] ;
}

cout << endl;

for (int i=0;i<3;i++)
for (int j=0; j<3; j++)
{
path+="Element:";
cout<<j<<" "<<i<<endl;
getpath(path, j,i,"first",0);



path = "";

}


}

Ошибка 1 error C2446: !=: нет преобразования "const char *" в "int" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 16
Ошибка 2 error C2040: !=: "int" отличается по уровням косвенного обращения от "const char [5]" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 16
Ошибка 3 error C2664: getpath: невозможно преобразовать параметр 1 из "const char [7]" в "char" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 19
Ошибка 4 error C2446: !=: нет преобразования "const char *" в "int" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 21
Ошибка 5 error C2040: !=: "int" отличается по уровням косвенного обращения от "const char [6]" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 21
Ошибка 6 error C2664: getpath: невозможно преобразовать параметр 1 из "const char [6]" в "char" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 24
Ошибка 7 error C2446: !=: нет преобразования "const char *" в "int" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 26
Ошибка 8 error C2040: !=: "int" отличается по уровням косвенного обращения от "const char [5]" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 26
Ошибка 9 error C2664: getpath: невозможно преобразовать параметр 1 из "const char [4]" в "char" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 29
Ошибка 10 error C2446: !=: нет преобразования "const char *" в "int" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 31
Ошибка 11 error C2040: !=: "int" отличается по уровням косвенного обращения от "const char [3]" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 31
Ошибка 12 error C2664: getpath: невозможно преобразовать параметр 1 из "const char [6]" в "char" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 34
Ошибка 13 error C2446: !=: нет преобразования "const char *" в "int" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 37
Ошибка 14 error C2040: !=: "int" отличается по уровням косвенного обращения от "const char [9]" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 37
Ошибка 15 error C2664: getpath: невозможно преобразовать параметр 1 из "std::string" в "char" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 63
16 IntelliSense: несовместимые типы операндов ("char" и "const char *") c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 16
17 IntelliSense: аргумент типа "const char *" несовместим с параметром типа "char" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 19
18 IntelliSense: аргумент типа "const char *" несовместим с параметром типа "char" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 19
19 IntelliSense: несовместимые типы операндов ("char" и "const char *") c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 21
20 IntelliSense: аргумент типа "const char *" несовместим с параметром типа "char" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 24
21 IntelliSense: аргумент типа "const char *" несовместим с параметром типа "char" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 24
22 IntelliSense: несовместимые типы операндов ("char" и "const char *") c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 26
23 IntelliSense: аргумент типа "const char *" несовместим с параметром типа "char" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 29
24 IntelliSense: аргумент типа "const char *" несовместим с параметром типа "char" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 29
25 IntelliSense: несовместимые типы операндов ("char" и "const char *") c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 31
26 IntelliSense: аргумент типа "const char *" несовместим с параметром типа "char" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 34
27 IntelliSense: аргумент типа "const char *" несовместим с параметром типа "char" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 34
28 IntelliSense: несовместимые типы операндов ("char" и "const char *") c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 37
29 IntelliSense: не существует подходящей функции преобразования из "std::string" в "char" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 63
30 IntelliSense: аргумент типа "const char *" несовместим с параметром типа "char" c:\users\1\documents\visual studio 2010\projects\defense\defense\gfd.cpp 63
0
chizz
981 / 496 / 54
Регистрация: 19.03.2013
Сообщений: 3,095
Записей в блоге: 18
Завершенные тесты: 1
23.04.2013, 17:01 #15
Ну во-первых, используйте оформление кода, когда вставляете его в сообщение.
Во-вторых читайте про передача char в функцию

Блин, подпись скоммуниздили редиски.. Вообщем поищите инфу.
0
23.04.2013, 17:01
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.04.2013, 17:01
Привет! Вот еще темы с ответами:

Обход матрицы по спирали - C++
Пожалуйста, подскажите как должен выглядеть листинг к такой программе!? Обойти по спирали, начиная с центра, все элементы квадратной...

Вывести на экран все элементы заданного столбца матрицы большие заданного числа - C++
помогите пожалуйста,завтра последний день( 1)Дан двумерный массив. Вывести на экран все элементы s-го столбца массива, больше k.

Выполнить обход матрицы по спирали - C++
Здійснити обхід матриці по спіралі за годинниковою стрілкою, починаючи від ЇЇ лівого верхнього кута. Вивести елементи матриці у порядку...

Указатель на функцию и обход матрицы по спирали - C++
Всем привет, впервые столкнулся с такой задачей, не могли бы помочь с решением? Так же не совсем понятно задание. Особенно прототип функции...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru