http://mendo.mk/jforum/posts/list/6.page JForum - http://www.jforum.net За првито тест пример ми дава 4, 4 а треба 1, 3.
Видов на 4, 4 (т.е 3, 3) наводнува 3 цвеќиња и на 1, 3 (т.е 0, 2) наводнува 3 цвеќиња. А направено ми е само ако најде нешто повеќе цвеќиња да смене локација бидејќи пишува ако има повеќе решенија да се испечати она најлево. Help :?: :?:

[code]#include <bits/stdc++.h>
using namespace std;

int M, N, W;
string G[1000][1000];
int poseteno[1000][1000] = {0};


bool valid_move(pair<int, int> next)
{
return (next.first >= 0 && next.first < M && next.second >= 0 && next.second < N && G[next.first][next.second][0] != '#');
}

vector<pair<int, int> > possible_moves(pair<int, int> next)
{
vector<pair<int, int> > moves;
moves.push_back(make_pair(next.first, next.second+1));
moves.push_back(make_pair(next.first, next.second-1));
moves.push_back(make_pair(next.first+1, next.second));
moves.push_back(make_pair(next.first-1, next.second));
return moves;
}

int BFS(pair<int, int> sys)
{
int N = 0;
memset(poseteno, 0, sizeof(poseteno));
queue<pair<int, int> > red;
queue<int> far;
far.push(0);
red.push(sys);
while(!red.empty())
{
pair<int, int> node = red.front();
int mom = far.front();
red.pop();
vector<pair<int, int> > moves = possible_moves(node);
for(auto next : moves)
{
if(valid_move(next))
{
if(poseteno[next.first][next.second] == 0)
{
poseteno[next.first][next.second] = 1;
red.push(next);
far.push(mom+1);
if(mom+1 <= W)
{
if(G[next.first][next.second][0] == 'C') N++;
}
else
{
return N;
}
}
}
}
}
return N;
}


main()
{
cin >> M >> N;
cin >> W;

string GR[M];
for(int i = 0; i < M; i++)
{
cin >> GR[i];
}
for(int i = 0; i < M; i++)
{
for(int j = 0; j < N; j++)
{
G[i][j] = GR[i][j];
}
}
int L = 0, P, I, J;
for(int i = 0; i < M; i++)
{
for(int j = 0; j < N; j++)
{
if(G[i][j][0] == '.')
{
P = BFS(make_pair(i, j));
if(P > L)
{
I = i;
J = j;
}
}
}
}
cout << I+1 << " " << J+1;
return 0;
}
[/code]]]> http://mendo.mk/jforum/posts/preList/555/3391.page http://mendo.mk/jforum/posts/preList/555/3391.page GMT
[code]#include <bits/stdc++.h>
using namespace std;

int M, N, W;
string G[1000][1000];
int poseteno[1000][1000] = {0};


bool valid_move(pair<int, int> next)
{
return (next.first >= 0 && next.first < M && next.second >= 0 && next.second < N && G[next.first][next.second][0] != '#');
}

vector<pair<int, int> > possible_moves(pair<int, int> next)
{
vector<pair<int, int> > moves;
moves.push_back(make_pair(next.first, next.second+1));
moves.push_back(make_pair(next.first, next.second-1));
moves.push_back(make_pair(next.first+1, next.second));
moves.push_back(make_pair(next.first-1, next.second));
return moves;
}

int BFS(pair<int, int> sys)
{
int N = 0;
memset(poseteno, 0, sizeof(poseteno));
queue<pair<int, int> > red;
queue<int> far;
far.push(0);
red.push(sys);
while(!red.empty())
{
pair<int, int> node = red.front();
int mom = far.front();
red.pop();
far.pop();
vector<pair<int, int> > moves = possible_moves(node);
for(auto next : moves)
{
if(valid_move(next))
{
if(poseteno[next.first][next.second] == 0)
{
poseteno[next.first][next.second] = 1;
red.push(next);
far.push(mom+1);
if(mom+1 <= W)
{
if(G[next.first][next.second][0] == 'C') N++;
}
else
{
return N;
}
}
}
}
}
return N;
}


main()
{
cin >> M >> N;
cin >> W;

string GR[M];
for(int i = 0; i < M; i++)
{
cin >> GR[i];
}
for(int i = 0; i < M; i++)
{
for(int j = 0; j < N; j++)
{
G[i][j] = GR[i][j];
}
}
int L = 0, P, I, J;
for(int i = 0; i < M; i++)
{
for(int j = 0; j < N; j++)
{
if(G[i][j][0] == '.')
{
P = BFS(make_pair(i, j));
if(P > L)
{
L = P;
I = i;
J = j;
}
}
}
}
cout << I+1 << " " << J+1;
return 0;
}
[/code]]]> http://mendo.mk/jforum/posts/preList/555/3392.page http://mendo.mk/jforum/posts/preList/555/3392.page GMT Многу BFS-а се тоа.
Ако ја прочиташ задачата уште еднаш, ќе видиш дека K <= 100, и всушност можеш да почнеш со BFS од тие позиции. Тоа е многу помал број од M*N.]]> http://mendo.mk/jforum/posts/preList/555/3393.page http://mendo.mk/jforum/posts/preList/555/3393.page GMT Многу BFS-а се тоа.
Ако ја прочиташ задачата уште еднаш, ќе видиш дека K <= 100, и всушност можеш да почнеш со BFS од тие позиции. Тоа е многу помал број од M*N.[/quote]

Ја пишував од ново со BFS од цвеќињата ама па нејќе неможам да си ја најдам грешката :/

[code]#include <bits/stdc++.h>
using namespace std;
int N, M, W, BC = 0;
string G[1000][1000];
int poseteno[1000][1000] = {0};
int matrix[1000][1000] = {0};
queue<pair<int, int> > red;
queue<int> far;

bool valid_move(pair<int, int> next)
{
return (next.first >= 0 && next.first < N && next.second >= 0 && next.second < M && G[next.first][next.second][0] != '#' && G[next.first][next.second][0] != 'C');
}

vector<pair<int, int> >possible_moves(pair<int, int> node)
{
vector<pair<int, int> > moves;
moves.push_back(make_pair(node.first, node.second+1));
moves.push_back(make_pair(node.first, node.second-1));
moves.push_back(make_pair(node.first+1, node.second));
moves.push_back(make_pair(node.first-1, node.second));
return moves;
}

void BFS()
{
while(!red.empty())
{
int mom = far.front();
far.pop();
pair<int, int> node = red.front();
red.pop();
vector<pair<int, int> > moves = possible_moves(node);
for(pair<int, int> next : moves)
{
if(valid_move(next))
{
if(mom+1 >= W) break;
if(poseteno[next.first][next.second] == 0)
{
poseteno[next.first][next.second] = poseteno[next.first][next.second]+1;
red.push(next);
far.push(mom+1);
}
matrix[next.first][next.second] = matrix[node.first][node.second]+1;
}
}
}
}

main()
{
cin >> N >> M;
cin >> W;
string GR[N];
for(int i = 0; i < N; i++) cin >> GR[i];
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
G[i][j] = GR[i][j];
if(G[i][j][0] == 'C')
{
red.push(make_pair(i, j));
far.push(0);
BC++;
}
}
}
BFS();
int NG = 0;
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
NG = max(NG, matrix[i][j]);
}
}
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
if(matrix[i][j] == NG)
{
cout << i+1 << " " << j+1;
return 0;
}
}
}
return 0;
}
[/code]]]> http://mendo.mk/jforum/posts/preList/555/3395.page http://mendo.mk/jforum/posts/preList/555/3395.page GMT Еве поправки. Ако добро сфатив што сакаш да искуцаш, мислам дека не може да ги ставиш така во ред сите на почеток, бидејќи потоа незнаеш со poseteno[][] дали да продолжиш или не (бидејќи секое цвеќе е посебно).
[code]#include <bits/stdc++.h>
using namespace std;
int N, M, W, BC = 0;
string G[1000][1000];
int poseteno[1000][1000] = {0};
int matrix[1000][1000] = {0};
queue<pair<int, int> > red;
queue<int> far;

bool valid_move(pair<int, int> next)
{
return (next.first >= 0 && next.first < N && next.second >= 0 && next.second < M && G[next.first][next.second][0] != '#');
}

vector<pair<int, int> >possible_moves(pair<int, int> node)
{
vector<pair<int, int> > moves;
moves.push_back(make_pair(node.first, node.second+1));
moves.push_back(make_pair(node.first, node.second-1));
moves.push_back(make_pair(node.first+1, node.second));
moves.push_back(make_pair(node.first-1, node.second));
return moves;
}

void BFS()
{
memset(poseteno, 0, sizeof(poseteno));

while(!red.empty())
{
int mom = far.front();
far.pop();
pair<int, int> node = red.front();
red.pop();
vector<pair<int, int> > moves = possible_moves(node);
for(pair<int, int> next : moves)
{
if(valid_move(next))
{
if(mom+1 > W) break;
if(poseteno[next.first][next.second] == 0)
{
poseteno[next.first][next.second] = poseteno[next.first][next.second]+1;
red.push(next);
far.push(mom+1);

matrix[next.first][next.second] = matrix[next.first][next.second]+1;
}
}
}
}
}

int main()
{
cin >> N >> M;
cin >> W;
string GR[N];
for(int i = 0; i < N; i++) cin >> GR[i];

for(int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
G[i][j] = GR[i][j];

for(int i = 0; i < N; i++)
for(int j = 0; j < M; j++)
{
if(G[i][j][0] == 'C')
{
red.push(make_pair(i, j));
far.push(0);
BC++;

BFS();
}
}

int NG = 0;
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
NG = max(NG, matrix[i][j]);
}
}
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
if(matrix[i][j] == NG)
{
cout << i+1 << " " << j+1;
return 0;
}
}
}
return 0;
}[/code]]]> http://mendo.mk/jforum/posts/preList/555/3396.page http://mendo.mk/jforum/posts/preList/555/3396.page GMT