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

Обход доски - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
12.09.2010, 22:28     Обход доски #1
есть фигура, которая может ходить вперед, вперед-влево, вперед-вправо, назад-влево и назад-вправо ка показано на рисунке.

даны координаты этой фигуры а также координаты финиша.
на пути у фигуры есть преграды их координаты тоже даны.
нужно определить за какое минимальное количество ходов фигура пройдет от старта до финиша

пример
координаты старта 2 2
координаты финиша 4 4
координаты препятствий 3 3, 4 3, 5 1
количество ходов(шагов) 4
путь на рисунку (САМ РИСОВАЛ)
Миниатюры
Обход доски   Обход доски  
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
12.09.2010, 22:35     Обход доски #2
http://www.youtube.com/watch?v=30xha...D5BB4&index=38(1)
http://www.youtube.com/watch?v=3MQwg...D5BB4&index=39(2)
Посмотри,может что пригодитсо.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
12.09.2010, 22:37  [ТС]     Обход доски #3
могу выложить исходники, что получилось у меня (использовал очередь и векторы в качестве доски)
но не работает ...
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
12.09.2010, 22:39     Обход доски #4
Mayonez,
Ну так а если есть исходники, то почему мы их ещё не лицезрели?
Тут всё-таки принято выкладывать свои наработки и содержательные вопросы, а не "почему не работает"...
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
12.09.2010, 22:50  [ТС]     Обход доски #5
если что-то разберете
даные читал из файлика input.txt
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
#include <queue>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
 
bool check(int x, int y, vector<vector<int> > a, vector<vector<bool> > b, int xSz, int ySz);
 
int main()
{
   ifstream fin("input.txt");
   int xst, yst, xfn, yfn, xSz, ySz;
   fin>>xst>>yst>>xfn>>yfn>>xSz>>ySz;
   vector<vector<int> > board(xSz);
   vector<vector<bool> > b2;
   b2.resize(xSz);
//------------------------------------------------------------------------------
   for(int i=0; i<xSz; i++)
   {
      b2[i].resize(ySz);
      for(int j=0; j<ySz; j++)
         b2[i][j]=0;
   }
   for(int i=0; i<xSz; i++)
   {
      board[i].resize(ySz);
      for(int j=0; j<ySz; j++)
         board[i][j]=0;
   }
//------------------------------------------------------------------------------
   int k;
   fin>>k;
   int Xk, Yk;
   for(int i=0; i<k; i++)
   {
      fin>>Xk>>Yk;
      board[Xk-1][Yk-1]=1;
   }
//------------------------------------------------------------------------------
   queue<pair<pair<int,int>,int> > q;
   pair<pair<int,int>,int> now;
   q.push(make_pair(make_pair(xst-1, yst-1), 0));
   int how=-1;
   while(!q.empty())
   {
      now=q.front();
      q.pop();
      if(now.first.first==xfn-1 && now.first.second==yfn-1) 
      {
         how=now.second;
         break;
      }
      if(check(now.first.first, now.first.second+1, board, b2, xSz, ySz))
      {
         q.push(make_pair(make_pair(now.first.first, now.first.second+1), now.second+1));
         b2[now.first.first][now.first.second+1]=1;
      }
      if(check(now.first.first+1, now.first.second+1, board, b2, xSz, ySz))
      {
         q.push(make_pair(make_pair(now.first.first+1, now.first.second+1), now.second+1));
         b2[now.first.first+1][now.first.second+1]=1;
      }
      if(check(now.first.first-1, now.first.second+1, board, b2, xSz, ySz))
      {
         q.push(make_pair(make_pair(now.first.first-1, now.first.second+1), now.second+1));
         b2[now.first.first-1][now.first.second+1]=1;
      }
      if(check(now.first.first-1, now.first.second-1, board, b2, xSz, ySz))
      {
         q.push(make_pair(make_pair(now.first.first, now.first.second+1), now.second+1));
         b2[now.first.first-1][now.first.second-1]=1;
      }
      if(check(now.first.first+1, now.first.second-1, board, b2, xSz, ySz))
      {
         q.push(make_pair(make_pair(now.first.first, now.first.second+1), now.second+1));
         b2[now.first.first+1][now.first.second-1]=1;
      }
   }
//------------------------------------------------------------------------------
   cout<<how;
   return 0;
}
 
bool check(int x, int y, vector<vector<int> > a, vector<vector<bool> > b, int xSz, int ySz)
{
   if(!(x<xSz) || !(y<ySz) || y<0 || x<0) return 0;
   if(a[x][y]==1 || b[x][y]==1) return 0;  
   return 1;
}
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
12.09.2010, 22:52     Обход доски #6
Mayonez,
Господи, ну что ж это... Во-первых, пользуйтесь тегами для оформления кода. Во-вторых, напишите наконец, что работает?
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
12.09.2010, 23:02  [ТС]     Обход доски #7
Цитата Сообщение от Asics^ Посмотреть сообщение
Посмотри,может что пригодитсо.
идея в принципе та же, но реализовать не получается
nail89
5 / 5 / 0
Регистрация: 28.07.2010
Сообщений: 12
12.09.2010, 23:10     Обход доски #8
Чем-то смахивает на алгоритм Форда Фалкерсона - просмотр всех доступных точек из каждой точки и составление всех возможных комбинаций путей
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
12.09.2010, 23:42     Обход доски #9
vector<vector<bool> > b2;

Зачем?
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
13.09.2010, 20:55  [ТС]     Обход доски #10
Цитата Сообщение от Lavroff Посмотреть сообщение
vector<vector<bool> > b2;
Зачем?
ну типа чтобы не возвращатся на клетку, где уже был(???)

Добавлено через 6 минут
подскажите, как сделать дерево, чтобы каждая ветка имела пять листей (пять возможных ходов)
тогда самый быстрый путь будет там, где меньше всего потомков
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
13.09.2010, 21:16     Обход доски #11
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
#include <fstream>
#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
ifstream cin("input.txt");
ofstream cout("output.txt");
 
typedef pair<int,int> ii;
 
const int dx[] = {-1,-1,-1, 1,1};
const int dy[] = {-1, 0, 1,-1,1};
const int wall = -1, not_visited = -2;
 
vector<vector<int> > field;
 
int main()
{
    int n, m;
    ii start, finish;
    cin >> n >> m;
    string dummy;
    getline(cin,dummy); // подскажите, как нормально пропустить перевод строки
    field.resize(n,vector<int>(m,not_visited));
    for(int i = 0; i < n; i++)
    {
        string s;
        getline(cin,s);
        for(int j = 0; j < s.size(); j++)
            if(s[j] == 's')
                start = ii(i,j);
            else if(s[j] == 'f')
                finish = ii(i,j);
            else if(s[j] == 'x')
                field[i][j] = wall;
    }
    queue<ii> q;
    q.push(start);
    field[start.first][start.second] = 0;
    while(!q.empty())
    {
        ii cur = q.front();
        q.pop();
        for(int d = 0; d < 5; d++)
        {
            int x = cur.first + dx[d], y = cur.second + dy[d];
            if(x >= 0 && x < n && y >= 0 && y < m && 
                field[x][y] == not_visited)
            {
                field[x][y] = field[cur.first][cur.second]+1;
                q.push(ii(x,y));
            }
        }
    }
    if(field[finish.first][finish.second] == not_visited)
        cout << "Fail";
    else
        cout << field[finish.first][finish.second];
}
input.txt:
Код
5 5
.....
...f.
..xx.
.s...
....x
output.txt:
Код
4
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
13.09.2010, 21:24  [ТС]     Обход доски #12
спасибо

string dummy;
getline(cin,dummy); // подскажите, как нормально пропустить перевод строки
просто убрать эти две строчки, разве нет?
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
13.09.2010, 21:25     Обход доски #13
Нет .
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
13.09.2010, 22:05  [ТС]     Обход доски #14
тогда получай не строку (getline) а просто по одному символу и если обнаружен символ перехода на новую строку, заполнять следующую строчку
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.09.2010, 22:08     Обход доски
Еще ссылки по теме:

Нужно написать обход шахматной доски конем. На одну позицию можно стать один раз. Обеспечить алгоритм бектрекингу C++
C++ Задачка. Поле шахматной доски
Разница между понятиями "Обход в прямом направлении" и "Итерационный прямой обход" C++

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

Или воспользуйтесь поиском по форуму:
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
13.09.2010, 22:08     Обход доски #15
Да, там можно забить на строку и читать посимвольно, я просто сначала хотел пустые клетки пробелами обозначать, потом забил и точками заполнил.
Yandex
Объявления
13.09.2010, 22:08     Обход доски
Ответ Создать тему
Опции темы

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