Cod sursa(job #2144800)

Utilizator butasebiButa Gabriel-Sebastian butasebi Data 26 februarie 2018 22:14:12
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <bits/stdc++.h>
using namespace std;
int minn = INT_MAX, n, m, i, j, v[105][105], w[105][105];
const int ln[] = {0, 0, -1, 1, 1, 1, -1, -1};
const int col[] = {1, -1, 0, 0, -1, 1, -1, 1};
char c, s[1005];
struct Lee
{
    int lin;
    int col;
}val, R, J, val1, poz;
deque <Lee>Q;
int main()
{
    ifstream f("rj.in");
    ofstream g("rj.out");
    f >> n >> m;
    f.getline(s, sizeof(s));
    for(i = 1;i <= n;i++)
    {
        f.getline(s, sizeof(s));
        for(j = 1;j <= m;j++)
        {
            c = s[j - 1];
            if(c == 'X')
            {
                v[i][j] = -1;
                w[i][j] = -1;
            }
            if(c == 'R')
            {
                R.lin = i;
                R.col = j;
            }
            if(c == 'J')
            {
                J.lin = i;
                J.col = j;
            }
        }
    }
    for(i = 0;i <= n + 1;i++)
        v[i][0] = v[i][m + 1] = w[i][0] = w[i][m + 1] = -1;
    for(j = 0;j <= m + 1;j++)
        v[0][j] = v[n + 1][j] = w[0][j] = w[n + 1][j] = -1;
    Q.push_back(R);
    v[R.lin][R.col] = 1;
    while(!Q.empty())
    {
        val = Q.front();
        Q.pop_front();
        for(i = 0;i < 8;i++)
        {
            val1.lin = val.lin + ln[i];
            val1.col = val.col + col[i];
            if(v[val1.lin][val1.col] == 0)
            {
                Q.push_back(val1);
                v[val1.lin][val1.col] = v[val.lin][val.col] + 1;
            }
        }
    }
    Q.push_back(J);
    w[J.lin][J.col] = 1;
    while(!Q.empty())
    {
        val = Q.front();
        Q.pop_front();
        for(i = 0;i < 8;i++)
        {
            val1.lin = val.lin + ln[i];
            val1.col = val.col + col[i];
            if(w[val1.lin][val1.col] == 0)
            {
                Q.push_back(val1);
                w[val1.lin][val1.col] = w[val.lin][val.col] + 1;
            }
        }
    }
    for(i = 1;i <= n;i++)
        for(j = 1;j <= m;j++)
            if(v[i][j] > 0 && w[i][j] == v[i][j] && w[i][j] < minn)
            {
                minn = w[i][j];
                poz.lin = i;
                poz.col = j;
            }
    g << minn << " " << poz.lin << " " << poz.col;
    return 0;
}