Cod sursa(job #1855391)

Utilizator TincaMateiTinca Matei TincaMatei Data 23 ianuarie 2017 17:03:22
Problema Car Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <cstdio>
#include <queue>

const int MAX_N = 500;
bool trec[1+MAX_N+1][1+MAX_N+1];
int dist[8][1+MAX_N+1][1+MAX_N+1];
const int INF = 1000000000;

struct Punct {
  int l, c, dir;
};

std::queue<Punct> q;

int dl[] = {1, 1, 0, -1, -1, -1, 0, 1};
int dc[] = {0,-1, -1,-1,  0,  1, 1, 1};

int main() {
	int n, m, l1, c1, l2, c2;
	FILE *fin = fopen("car.in", "r");
	fscanf(fin, "%d%d%d%d%d%d", &n, &m, &l1, &c1, &l2, &c2);
	for(int l = 1; l <= n; ++l)
	  for(int c = 1; c <= m; ++c) {
	    fscanf(fin, "%d", &trec[l][c]);
		  for(int i = 0; i < 8; ++i)
		    dist[i][l][c] = INF;
	  }
	fclose(fin);
  for(int i = 0; i < 8; ++i) {
    dist[i][l1][c1] = 0;
	  q.push({l1, c1, i});
	}

  while(!q.empty()) {
    int l = q.front().l;
    int c = q.front().c;
    int dir = q.front().dir;
    q.pop();
    for(int i = 0; i < 4; ++i) {
      int dir2 = (dir + i) % 8;
      int ln = l + dl[dir2];
      int cn = c + dc[dir2];
      if(1 <= ln && ln <= n && 1 <= cn && cn <= m)
				if(!trec[ln][cn] && dist[dir][l][c] + i < dist[dir2][ln][cn]) {
					dist[dir2][ln][cn] = dist[dir][l][c] + i;
					q.push({ln, cn, dir2});
				}
      dir2 = (dir - i + 8) % 8;
      ln = l + dl[dir2];
      cn = c + dc[dir2];
      if(1 <= ln && ln <= n && 1 <= cn && cn <= m)
				if(!trec[ln][cn] && dist[dir][l][c] + i < dist[dir2][ln][cn]) {
					dist[dir2][ln][cn] = dist[dir][l][c] + i;
					q.push({ln, cn, dir2});
				}
    }
  }

	FILE *fout = fopen("car.out", "w");
	int min = 1000000000;
	for(int i = 0; i < 8; ++i)
	  if(dist[i][l2][c2] < min)
	    min = dist[i][l2][c2];

	if(min == INF)
	  fprintf(fout, "-1");
	else
	  fprintf(fout, "%d", min);
	fclose(fout);
	return 0;
}