www.spoj.pl/problems/SHOP
Its a pretty easy Q... But m not able to figure out any silly mistake
in my prog.. plzz help
#include<iostream>
#include<vector>
#include<map>
#include<queue>
using namespace std;
char a[26][26];
int si, sj, di, dj, rows, cols;
void BFS(vector< vector<int> > &v, int si, int sj, int rows, int
cols);
int safe(vector< vector<int> > &v, int r, int c, int current, int
rows, int cols);
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int si, sj;
while(1)
{
cin >> cols >> rows;
if(rows == 0 && cols == 0)
break;
vector<int> row(26, INT_MAX);
vector< vector<int> > final(26, row);
for(int i=0; i<rows; i++)
for(int j=0; j<cols; j++)
{
cin >> a[i][j];
if(a[i][j] == 'S')
{
si = i; sj = j;
}
else if(a[i][j] == 'D')
{
di = i; dj = j;
a[i][j] = '0';
}
}
BFS(final, si, sj, rows, cols);
cout << final[di][dj] << endl;
/*
for(int i=0; i<rows; i++)
{
for(int j=0; j<cols; j++)
cout << final[i][j] << " ";
cout << endl;
}
cout << endl;
*/
}
return 0;
}
void BFS(vector< vector<int> > &v, int si, int sj, int rows, int cols)
{
pair<int, int> p;
queue< pair<int, int> > q;
q.push(make_pair(si, sj));
v[si][sj] = 0;
while(!q.empty())
{
p = q.front(); q.pop();
int current = v[p.first][p.second];
if(safe(v, p.first+1, p.second, current, rows, cols))
q.push(make_pair(p.first+1, p.second));
if(safe(v, p.first-1, p.second, current, rows, cols))
q.push(make_pair(p.first-1, p.second));
if(safe(v, p.first, p.second+1, current, rows, cols))
q.push(make_pair(p.first, p.second+1));
if(safe(v, p.first, p.second-1, current, rows, cols))
q.push(make_pair(p.first, p.second-1));
}
}
int safe(vector< vector<int> > &v, int r, int c, int current, int
rows, int cols)
{
if(r >= 0 && r < rows && c >= 0 && c < cols && a[r][c] != 'X')
{
if(v[r][c] > current + a[r][c] - '0')
{
v[r][c] = current + a[r][c] - '0';
return 1;
}
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
