#include #include #define MAXMN 1000 #define MAXK 10000 //konstanty pro překážku na políčku #define PREKAZKA -3 //a nedosažené políčko #define NEDOSAZENO -2 //rozměry M x N, počet překážek, zdroj a cíl int M, N, K, startX, startY, cilX, cilY; //pole udavající, přes kolik zrcadel se světlo //dostane na políčko (-2 = ještě se tam nedostalo, //-3 = překážka) int sit[MAXMN][MAXMN]; //pole, udávající, jestli světo letělo políčkem //horizontálním či vertikálním směrem //(0 = žádným směrem, 1 = jen horizontálně, //2 = jen vertikálně, 3 = letělo oběma směry) int smery[MAXMN][MAXMN]; //fronta na prohledávání do šířky //(pro přehlednost používám 2 pole, políčka se ale //dají kódovat jako (y - 1) * M + x do jednoho) int frontaX[MAXMN * MAXMN], frontaY[MAXMN * MAXMN]; int frStart, frKon; //projde políčka od [x, y] ve směru (dx, dy) //dokud nenarazí na překážku void projdi(int x, int y, int dx, int dy) { int i = 1, nx = x + i * dx, ny = y + i * dy; while (nx > 0 && ny > 0 && nx <= M && ny <= N && sit[nx][ny] != PREKAZKA) { //políčko [nx, ny] ještě nebylo dosaženo if (sit[nx][ny] == NEDOSAZENO) { //je třeba o 1 zrcadlo více sit[nx][ny] = sit[x][y] + 1; //zařaď políčko do fronty frontaX[frKon] = nx; frontaY[frKon++] = ny; } //políčkem už prošlo světlo horizontálně if (dx != 0) smery[nx][ny] += 1; //nebo vertikálně else if (dy != 0) smery[nx][ny] += 2; //posuň se dále i++; nx = x + i * dx; ny = y + i * dy; } } int main(void) { scanf("%d %d %d", &M, &N, &K); scanf("%d %d", &startX, &startY); scanf("%d %d", &cilX, &cilY); //inicializace for (int i = 1; i <= M; i++) for (int j = 1; j <= N; j++) { smery[i][j] = 0; sit[i][j] = NEDOSAZENO; } //načti překážky a přidej je do sítě int a,b; for (int i = 0; i < K; i++) { scanf("%d %d", &a, &b); sit[a][b] = PREKAZKA; } //inicializace fronty frStart = 0; frKon = 1; frontaX[0] = startX; frontaY[0] = startY; sit[startX][startY] = -1; int x, y; //dokud je ve frontě ještě nějaký prvek //a cíl nedosažen while (frStart < frKon && sit[cilX][cilY] == NEDOSAZENO) { //vytáhni políčko z fronty x = frontaX[frStart]; y = frontaY[frStart++]; //neletělo-li políčkem světlo horizontálně if ((smery[x][y] & 1u) == 0) { //projdi políčka od něj vlevo i vpravo projdi(x, y, 1, 0); projdi(x, y, -1, 0); } //to samé pro vertikální směr if ((smery[x][y] & 2u) == 0) { projdi(x, y, 0, 1); projdi(x, y, 0, -1); } //světlo letělo z tohoto políčka všemi směry smery[x][y] = 3; } if (sit[cilX][cilY] == NEDOSAZENO) { printf("Cílové políčko je nedosažitelné.\n"); } else { printf("Je třeba umístit %d zrcadel.\n", sit[cilX][cilY]); } return 0; }