#include #include #include using std::max; using std::stack; #define MAX 1047 // hodnota policka int F[MAX][MAX]; // podvadzacie policko bool G[MAX][MAX]; // cislo silno-suvislej komponenty v ktorej je policko int C[MAX][MAX]; // suma v danej komponente int H[MAX*MAX]; // najdrahsia cesta konciaca v danej komponente int R[MAX*MAX]; // navstivene vrcholy v DFS1 a DFS2 bool V1[MAX][MAX]; bool V2[MAX][MAX]; int X, Y, K; typedef struct { int x, y; } Point; stack S; // je miestnost na mape ? bool Valid(int x, int y) { return x >= 1 && x <= X && y >= 1 && y <= Y; } void DFS1(int x, int y) { if (!Valid(x,y) || V1[y][x]) return; V1[y][x] = true; DFS1(x+1,y); DFS1(x,y+1); if (G[y][x]) { DFS1(x-1,y); DFS1(x,y-1); } S.push((Point){x,y}); } void DFS2(int x, int y, int c) { if (!Valid(x,y)) return; // ak sme prekrocili hranicu komponenty // skontrolovat existenciu drahsej cesty // do povodnej komponenty if (c != C[y][x]) R[c] = max(R[c], R[C[y][x]]); if (V2[y][x]) return; V2[y][x] = true; C[y][x] = c; // hodnotu policka pripocitat k sume komponenty H[c] += F[y][x]; DFS2(x-1,y,c); DFS2(x,y-1,c); if (G[y][x+1]) DFS2(x+1,y,c); if (G[y+1][x]) DFS2(x,y+1,c); } int main() { // naitat mapu scanf("%d %d %d", &Y, &X, &K); for (int y = 1; y <= Y; y++) for (int x = 1; x <= X; x++) scanf("%d", &F[y][x]); // nacitat podvadzacie policka for (int x, y, i = 0; i < K; i++) { scanf("%d %d", &x, &y); G[y][x] = true; } // prehladat transponovany graf a zoradit vrcholy // podla klesajuceho casu opustenia for (int y = 1; y <= Y; y++) for (int x = 1; x <= X; x++) DFS1(x,y); // prejst vrcholy v poradi klesajuceho casu opustenia, // oznacit silno-suvisle komponenty a rovno spocitat // najdrahsiu cestu konciacu v danej komponente for (int i = 1; i <= X*Y; i++) { DFS2(S.top().x,S.top().y,i); S.pop(); R[i] += H[i]; } printf("%d\n", R[C[Y][X]]); return 0; }