Jde mi o to seřadit to tím vyřazováním (vyřazuju čísla dokud to není tak jak má - stoupá - vrchol - klesá). Příklad - 1 8 2 3 4 8 6 - 1 2 3 4 8 6 (škrtnu 8) - chci vyškrtnout co nejmíň čísel tak aby to splňovalo ty podmínky.
Příspěvky odeslané z IP adresy 89.190.52.–
Ahoj, snažím se setřídit velké množství čísel seškrtáváním tak abych našel nejvyšší číslo a od něj čísla na obě strany klesaly(rostoucí čísla - nejvyšší číslo - klesající čísla). Nejlepší postup co mě napadl je zredukovat duplikáty (všechna stejná čísla nahradit jedním - 1, 2, 2, 2, 3, 5 = 1, 2, 3, 5), potom najít nejvyšší číslo "zprava" (1, 8, 2, 3, 4, 8, 5, 6, 8, 1) a od něj to porovnávat doprava i doleva menší než (1 < 8 < 2 < 3 < 4 < 8 < 5 < 6 < 8 >1) - 2 "vyškrtnutí". Nemáte lepší postup?(nejde mi o rychlost ale o co nejmíň vyřazených čísel)
Díky
To je na mě trochu moc... A nešlo by třeba si jenom určit nějak záchytný body? Příklad -
S#....#F S # 6 7 8 9 # F .#.##.#. 1 # 5 # # 10# 10 ........ označím jako 2 3 4 5 6 7 8 9 #.##.# 5 # # 12 ..#. 6 7 # 11
... 8 9 10
Tady bych ho udělal na 7 a pak bych šel první cestu a při další skočil na nejnižší možnost (10) a pokračoval po ní a pak znova tu 12. Šlo by to takhle? Určil bych je asi tam kde by se jinak přepisovalo mensi cislo vetsim(ta 7) nebo to tak vychazi jen nahodou?
Zkusil jsem to ohodnocování pozic a funguje to dobře, ale napadá mě - dá se pak nějak dostat i ta zbylá cesta? Myslím jako vypsat všechny cesty z bludiště podle rychlosti(v tom příkladu nahoře nevím jak bych dostal tu delší - horem). Nebo na to bych musel nějak jinak? Díky
Ahoj, snažím se najít nejkratší cestu z bludiště prohledáváním do šířky. Program už projde všechny políčka a najde cíl, tady je kód:
#include <fstream>
#include <queue>
#include <iostream>
using std::queue;
struct s_maze
{
char place;
int c;
int r;
bool used;
};
int main()
{
using std::ifstream;
using std::ofstream;
ifstream fin;
ofstream fout;
fin.open("maze.in");
if (fin.is_open() == false)
return 0;
int row, column, start_c, start_r;
fin >> row >> column;
s_maze maze[50][50];
s_maze test_maze;
for (int c = 0; c < column; ++c)
{
for (int r = 0; r < row; ++r)
{
fin >> maze[c][r].place;
maze[c][r].used = false;
maze[c][r].c = c;
maze[c][r].r = r;
if (maze[c][r].place == 'S')
{
start_c = c;
start_r = r;
}
}
}
queue <s_maze> q;
q.push(maze[start_c][start_r]);
while(q.empty() != true)
{
test_maze = q.front();
maze[test_maze.c][test_maze.r].used = true;
std::cout << test_maze.c <<" " << test_maze.r << std::endl;
q.pop();
if (test_maze.place == 'C')
{
std::cout << "exit at " << test_maze.c << " " << test_maze.r;
std::cin.get();
return 0;
}
if (test_maze.c - 1 >= 0)
{
if (maze[test_maze.c - 1][test_maze.r].place != '#' && (maze[test_maze.c - 1][test_maze.r].place == '.' || maze[test_maze.c - 1][test_maze.r].place == 'S' || maze[test_maze.c - 1][test_maze.r].place == 'C') && (maze[test_maze.c - 1][test_maze.r].used == 0))
{
q.push(maze[test_maze.c - 1][test_maze.r]);
}
}
if (test_maze.c + 1 <= column)
{
if (maze[test_maze.c + 1][test_maze.r].place != '#' && (maze[test_maze.c + 1][test_maze.r].place == '.' || maze[test_maze.c + 1][test_maze.r].place == 'S' || maze[test_maze.c + 1][test_maze.r].place == 'C') && (maze[test_maze.c + 1][test_maze.r].used == 0))
{
q.push(maze[test_maze.c + 1][test_maze.r]);
}
}
if (test_maze.r + 1 <= row)
{
if (maze[test_maze.c][test_maze.r + 1].place != '#' && (maze[test_maze.c][test_maze.r + 1].place == '.' || maze[test_maze.c][test_maze.r + 1].place == 'S' || maze[test_maze.c][test_maze.r + 1].place == 'C') && (maze[test_maze.c][test_maze.r + 1].used == 0))
{
q.push(maze[test_maze.c][test_maze.r + 1]);
}
}
if (test_maze.r - 1 >= 0)
{
if (maze[test_maze.c][test_maze.r - 1].place != '#' && (maze[test_maze.c][test_maze.r - 1].place == '.' || maze[test_maze.c][test_maze.r - 1].place == 'S' || maze[test_maze.c][test_maze.r - 1].place == 'C') && (maze[test_maze.c][test_maze.r - 1].used == 0))
{
q.push(maze[test_maze.c][test_maze.r - 1]);
}
}
}
for (int c = 0; c < column; ++c)
{
for (int r = 0; r < row; ++r)
{
std::cout << maze[c][r].place;
}
std::cout << std::endl;
}
std::cout << start_r << " " << start_c;
std::cin.get();
return 0;
}
V tom maze.in je počet sloupců, řádků a bludiště -
8 3
S#....#F
.#.##.#.
........
Dá se nějak vylepšit ten vstup když mám velikost v souboru(abych nemusel používat 50x50 a testovat jestli je tam platný symbol)?
Jak bych měl sledovat cestu? Přemýšlím o lineárním spojovém seznamu ale nevím co dělat když se ty cesty větví - chci vypsat cestu v souřadnicích.
Díky