Pagini recente » Cod sursa (job #1047691) | Cod sursa (job #857179) | Cod sursa (job #2310399) | Cod sursa (job #1299011) | Cod sursa (job #1354393)
#include<fstream>
#include<queue>
#include<limits.h>
using namespace std;
int n,m, dp[255][255], xpaznic, ypaznic,maxim=INT_MIN;
char s[255][255];
const int dx[] = {0, 1, -1, 0};
const int dy[] = {1, 0, 0,-1};
queue < pair<int, int> > q;
ifstream fin("rj.in");
ofstream fout("rj.out");
bool inside(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void lee() {
/// q.push(make_pair(xpaznic, ypaznic)); /// bag primul paznic in coada
/// dp[xpaznic][ypaznic] = 0; /// pun distanta 0
while(!q.empty()) { // cat timp coada nu este goala
int x = q.front().first; /// lum coordonatele
int y = q.front().second;
q.pop(); /// scoatedin din coada primul element
for(int i = 0 ; i < 4 ; ++ i) { /// iau toti cei 4vecini
int newx = x + dx[i];
int newy = y + dy[i]; //// ii determin pe baza vectorilor delta
if(inside(newx, newy) && (dp[newx][newy] == -1 || dp[newx][newy] > dp[x][y] + 1)) { //// daca respecta conditiile adica: inauntrul matricei si celula nevizitat si liber (camera)
dp[newx][newy] = dp[x][y] + 1; /// determin noua distanta minima
q.push(make_pair(newx, newy)); /// bag la coada
}
}
}
for(int i = 1 ; i <= n ; ++ i)
for(int j = 1 ; j <= m ; ++ j)
if(dp[i][j]>maxim)
maxim=dp[i][j];
for(int i = 1 ; i <= n ; ++ i)
for(int j = 1 ; j <= m ; ++ j)
if(dp[i][j]==maxim) fout<<dp[i][j]<<" "<<i<<" "<<j;
}
int main ()
{
char sir[255];
fin >> n>>m;
fin.getline(sir,10);
for(int i =1 ; i <= n ; ++ i)
{
fin.getline(sir,255);
//fout<<sir<<"\n";
for(int j = 1 ; j <= m ; ++ j)
s[i][j]=sir[j-1];
}
/*for(int i = 1 ; i <= n ; ++ i)
for(int j = 1 ; j <= m ; ++ j) {
fin >> s[i][j];*/
for(int i = 1 ; i <= n ; ++ i)
for(int j = 1 ; j <= m ; ++ j)
if(s[i][j] == 'X')
dp[i][j] = -2;
else if(s[i][j] == ' ')
dp[i][j] = -1;
else {
/// avem paznic
q.push(make_pair(i, j)); /// il bagam in coada, care inainte de for(initial) era goala
dp[i][j] = 0; /// distanta 0 (distanta de start)
}
lee();
}
/**/