Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <fstream>
- using namespace std;
- ifstream fin("wow.in");
- ofstream fout("wow.out");
- int n, p, m, a[102][102], s[102][102], b[102][102];
- int dx[5] = {0, -1, 0, 1, 0};
- int dy[5] = {0, 0, 1, 0, -1};
- /*
- a - matricea mea initiala
- b - pe matricea b fac lee-ul
- s - suprapun lee-ul fiecarei pereche (x,y)
- Init() - pentru o noua pereche (x,y) matricea b ia valorile matricei a
- lee() - prelucreaza atat b-ul cat si s-ul
- Minim() - determin punctul minim in care se intalnesc perechile (x, y)
- */
- void Init()
- {
- int i, j;
- for(i = 0; i < n; i++)
- for(j = 0; j < p; j++)
- b[i][j] = a[i][j];
- }
- void Lee(int x, int y)
- {
- int pr, ul, x_curent, y_curent, x_vecin, y_vecin, i, j;
- int cx[100003], cy[100003];
- pr = ul = 1;
- cx[1] = x; cy[1] = y;
- Init();
- b[x][y] = 1;
- while(pr <= ul)
- {
- x_curent = cx[pr];
- y_curent = cy[pr];
- for(i = 1; i <= 4; i++)
- {
- x_vecin = x_curent + dx[i];
- y_vecin = y_curent + dy[i];
- if(x_vecin >= 0 && x_vecin < n && y_vecin >= 0 && y_vecin < p && b[x_vecin][y_vecin] == 0)
- {
- ul++;
- cx[ul] = x_vecin;
- cy[ul] = y_vecin;
- b[x_vecin][y_vecin] = b[x_curent][y_curent] + 1;
- }
- }
- pr++;
- }
- for(i = 0; i < n; i++)
- for(j = 0; j < p; j++)
- if(a[i][j] != 1) s[i][j] = s[i][j] + b[i][j];
- }
- void Minim()
- {
- int i, j, M = 2000000000, x, y;
- for(i = 0; i < n; i++)
- for(j = 0; j < p; j++)
- if(s[i][j] < M && a[i][j] != 1)
- {
- x = i;
- y = j;
- M = s[i][j];
- }
- fout << s[x][y] - m << "\n";
- fout << x << " " << y;
- }
- int main()
- {
- int i, x, y, j;
- fin >> n >> p >> m;
- for(i = 0; i < n; i++)
- for(j = 0; j < p; j++)
- fin >> a[i][j];
- for(i = 1; i <= m; i++)
- {
- fin >> x >> y;
- Lee(x, y);
- }
- Minim();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement