Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
148 lines (143 sloc) 6.12 KB
/*
* 8325 - Barareh on Fire
* ACM-ICPC Live Archive, Regionals 2017, Asia, Tehran
*
* Read Farsi solution guide: http://www.algorithmha.ir
*
*/
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m, k;
char board[100][100];
int status[100][100];
int route[100][100];
string temp;
const int max = 1000000;
vector<queue<pair<int, int>>> qs;
pair<int, int> source, dest;
while(true){
queue<pair<int, int>> mainQ;
qs.clear();
cin >> n >> m >> k;
if(n + m + k == 0)
break;
for(int i = 0; i < n; i++){
cin >> temp;
for(int j = 0; j < m; j++){
board[i][j] = temp[j];
route[i][j] = 1000000;
status[i][j] = (temp[j] == 'f' ? 0 : max);
if(temp[j] == 'f'){
queue<pair<int, int>> t;
t.push(pair<int, int>(i, j));
qs.push_back(t);
}
else if(temp[j] == 's')
source = pair<int,int>(i, j);
else if(temp[j] == 't')
dest = pair<int,int>(i, j);
}
}
int num = 1;
while (num != 0) {
num = 0;
for(int i = 0; i < qs.size(); i++){
if(qs[i].empty())
continue;
num++;
pair<int, int> p = qs[i].front();
qs[i].pop();
if(p.first > 0){
if(p.second > 0)
if(status[p.first - 1][p.second - 1] == max)
{
status[p.first - 1][p.second - 1] = status[p.first][p.second] + k;
qs[i].push(pair<int,int>(p.first - 1, p.second - 1));
}
if(status[p.first - 1][p.second] == max)
{
status[p.first - 1][p.second] = status[p.first][p.second] + k;
qs[i].push(pair<int,int>(p.first - 1, p.second));
}
if(p.second < m - 1)
if(status[p.first - 1][p.second + 1] == max)
{
status[p.first - 1][p.second + 1] = status[p.first][p.second] + k;
qs[i].push(pair<int,int>(p.first - 1, p.second + 1));
}
}
if(p.first < n - 1){
if(p.second > 0)
if(status[p.first + 1][p.second - 1] == max)
{
status[p.first + 1][p.second - 1] = status[p.first][p.second] + k;
qs[i].push(pair<int,int>(p.first + 1, p.second - 1));
}
if(status[p.first + 1][p.second] == max)
{
status[p.first + 1][p.second] = status[p.first][p.second] + k;
qs[i].push(pair<int,int>(p.first + 1, p.second));
}
if(p.second < m + 1)
if(status[p.first + 1][p.second + 1] == max)
{
status[p.first + 1][p.second + 1] = status[p.first][p.second] + k;
qs[i].push(pair<int,int>(p.first + 1, p.second + 1));
}
}
if(p.second > 0)
if(status[p.first][p.second - 1] == max)
{
status[p.first][p.second - 1] = status[p.first][p.second] + k;
qs[i].push(pair<int,int>(p.first, p.second - 1));
}
if(p.second < m - 1)
if(status[p.first][p.second + 1] == max)
{
status[p.first][p.second + 1] = status[p.first][p.second] + k;
qs[i].push(pair<int,int>(p.first, p.second + 1));
}
}
}
route[source.first][source.second] = 0;
mainQ.push(source);
while(!mainQ.empty()){
source = mainQ.front();
mainQ.pop();
if(source == dest)
break;
if(source.first > 0)
if(status[source.first - 1][source.second] > route[source.first][source.second] + 1 &&
route[source.first - 1][source.second] > route[source.first][source.second] + 1){
mainQ.push(pair<int,int>(source.first - 1, source.second));
route[source.first - 1][source.second] = route[source.first][source.second] + 1;
}
if(source.first < n - 1)
if(status[source.first + 1][source.second] > route[source.first][source.second] + 1 &&
route[source.first + 1][source.second] > route[source.first][source.second] + 1){
mainQ.push(pair<int,int>(source.first + 1, source.second));
route[source.first + 1][source.second] = route[source.first][source.second] + 1;
}
if(source.second > 0)
if(status[source.first][source.second - 1] > route[source.first][source.second] + 1 &&
route[source.first][source.second - 1] > route[source.first][source.second] + 1){
mainQ.push(pair<int,int>(source.first, source.second - 1));
route[source.first][source.second - 1] = route[source.first][source.second] + 1;
}
if(source.second < m - 1)
if(status[source.first][source.second + 1] > route[source.first][source.second] + 1 &&
route[source.first][source.second + 1] > route[source.first][source.second] + 1){
mainQ.push(pair<int,int>(source.first, source.second + 1));
route[source.first][source.second + 1] = route[source.first][source.second] + 1;
}
}
if(source == dest)
cout << route[dest.first][dest.second];
else
cout << "Impossible";
cout << endl;
}
return 0;
}