Cod sursa(job #2920755)

Utilizator AlexandruBenescuAlexandru Benescu AlexandruBenescu Data 25 august 2022 17:03:27
Problema Car Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <bits/stdc++.h>
#define L 505
#define DIR 8
#define BORDER -2
#define FREE 1000001
#define IMPOSSIBLE -1
using namespace std;

class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}

	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}

	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};

InParser fin("car.in");
ofstream fout("car.out");

int m[DIR][L][L], vx[DIR][L * L], vy[DIR][L * L], i1[DIR], i2[DIR];
int dl[DIR] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dc[DIR] = {0, 1, 1, 1, 0, -1, -1, -1};

int main(){
  int l, c, x, y, xx, yy, i, j, k, ok1, ok2, cost, res;
  fin >> l >> c >> x >> y >> xx >> yy;
  for (i = 1; i <= l; i++)
    for (j = 1; j <= c; j++){
      fin >> m[0][i][j];
      if (m[0][i][j] == 1)
        m[0][i][j] = BORDER;
      else
        m[0][i][j] = FREE;
      for (k = 1; k < DIR; k++)
        m[k][i][j] = m[0][i][j];
    }
  for (k = 0; k < DIR; k++){
    for (i = 0; i < l + 2; i++)
      m[k][i][0] = m[k][i][c + 1] = BORDER;
    for (j = 0; j < c + 2; j++)
      m[k][0][j] = m[k][l + 1][j] = BORDER;
  }
  res = FREE;
  if (m[0][x][y] == BORDER || m[0][xx][yy] == BORDER)
    res = IMPOSSIBLE;
  for (i = 0; i < DIR; i++){
    m[i][x][y] = 0;
    vx[i][i2[i]] = x;
    vy[i][i2[i]] = y;
    i2[i]++;
  }
  ok1 = ok2 = 1;
  while (ok1 && ok2){
    for (i = 0; i < DIR; i++){
      if (i1[i] < i2[i]){
        x = vx[i][i1[i]];
        y = vy[i][i1[i]];
        if (m[i][x + dl[i]][y + dc[i]] != BORDER && m[i][x + dl[i]][y + dc[i]] > m[i][x][y]){
          m[i][x + dl[i]][y + dc[i]] = m[i][x][y];
          vx[i][i2[i]] = x + dl[i];
          vy[i][i2[i]] = y + dc[i];
          i2[i]++;
        }
        for (j = 0; j < DIR; j++)
          if (j != i && j != (i + DIR / 2) % DIR){
            cost = min(abs(i - j), DIR - abs(i - j));
            if (m[j][x][y] > m[i][x][y] + cost){
              m[j][x][y] = m[i][x][y] + cost;
              vx[j][i2[j]] = x;
              vy[j][i2[j]] = y;
              i2[j]++;
            }
          }
        i1[i]++;
      }
    }
    ok1 = ok2 = 0;
    for (i = 0; i < DIR; i++){
      if (i1[i] < i2[i])
        ok1 = 1;
      if (m[i][xx][yy] == FREE)
        ok2 = 1;
    }
  }
  for (i = 0; i < DIR; i++)
    res = min(res, m[i][xx][yy]);
  if (res == FREE)
    res = IMPOSSIBLE;
  fout << res << "\n";
  return 0;
}