/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int K_MAX = 1000002;
struct Cell
{
int a, b;
};
int n, m;
vector <vector <int> > ma;
int k;
Cell v[K_MAX];
vector <vector <bool> > special;
bool inside (Cell c)
{
return (1 <= c.a && c.a <= n && 1 <= c.b && c.b <= m);
}
vector <vector <int> > pos;
vector <vector <bool> > visited;
int da[] = {-1, 0, 1, 0}, db[] = {0, 1, 0, -1};
bool dfs (int a, int b)
{
visited[a][b] = true;
for(int d = 0; d < 4; d++)
if(d != (pos[a][b] + 2) % 4)
{
int a1 = a + da[d] * 2, b1 = b + db[d] * 2;
if(inside(Cell{a1, b1}) == false || special[a1][b1] == false)
continue;
if(pos[a1][b1] != -1 && pos[a1][b1] != d)
return false;
if(visited[a1][b1] == true)
continue;
pos[a1][b1] = d;
if(dfs(a1, b1) == false)
return false;
}
return true;
}
int mi;
int cntu, cnte;
void dfs1 (int a, int b)
{
visited[a][b] = true;
cntu++;
for(int d = 0; d < 4; d++)
{
if(inside(Cell{a + da[d], b + db[d]}) == true)
mi = min(mi, ma[a + da[d]][b + db[d]]);
int a1 = a + da[d] * 2, b1 = b + db[d] * 2;
if(inside(Cell{a1, b1}) == false || special[a1][b1] == false)
continue;
cnte++;
if(visited[a1][b1] == true)
continue;
dfs1(a1, b1);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
ma.resize(n + 2);
for(int i = 0; i <= n + 1; i++)
ma[i].resize(m + 2);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> ma[i][j];
cin >> k;
for(int i = 1; i <= k; i++)
{
cin >> v[i].a >> v[i].b;
//v[i].a++;
//v[i].b++;
}
special.resize(n + 2);
for(int i = 0; i <= n + 1; i++)
special[i].resize(m + 2);
for(int i = 1; i <= k; i++)
special[v[i].a][v[i].b] = true;
pos.resize(n + 2);
for(int i = 0; i <= n + 1; i++)
pos[i].resize(m + 2);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
pos[i][j] = -1;
visited.resize(n + 2);
for(int i = 0; i <= n + 1; i++)
visited[i].resize(m + 2);
for(int i = 1; i <= k; i++)
{
if((v[i].a == 1 || v[i].a == n) && (v[i].b == 1 || v[i].b == m))
{
cout << "No\n";
return 0;
}
if(v[i].a == 1)
pos[v[i].a][v[i].b] = 2;
if(v[i].a == n)
pos[v[i].a][v[i].b] = 0;
if(v[i].b == 1)
pos[v[i].a][v[i].b] = 1;
if(v[i].b == m)
pos[v[i].a][v[i].b] = 3;
int aux = pos[v[i].a][v[i].b];
int cnt = 0;
if(inside(Cell{v[i].a - 1, v[i].b}) == true && special[v[i].a - 1][v[i].b] == true)
{
pos[v[i].a][v[i].b] = 2;
cnt++;
}
if(inside(Cell{v[i].a + 1, v[i].b}) == true && special[v[i].a + 1][v[i].b] == true)
{
pos[v[i].a][v[i].b] = 0;
cnt++;
}
if(inside(Cell{v[i].a, v[i].b - 1}) == true && special[v[i].a][v[i].b - 1] == true)
{
pos[v[i].a][v[i].b] = 1;
cnt++;
}
if(inside(Cell{v[i].a, v[i].b + 1}) == true && special[v[i].a][v[i].b + 1] == true)
{
pos[v[i].a][v[i].b] = 3;
cnt++;
}
if(cnt > 1 || (aux != -1 && pos[v[i].a][v[i].b] != aux))
{
cout << "No\n";
return 0;
}
}
for(int i = 1; i <= k; i++)
if(pos[v[i].a][v[i].b] != -1 && visited[v[i].a][v[i].b] == false)
{
if(dfs(v[i].a, v[i].b) == false)
{
cout << "No\n";
return 0;
}
}
for(int i = 1; i <= k; i++)
if(visited[v[i].a][v[i].b] == false)
{
if(inside(Cell{v[i].a - 1, v[i].b - 1}) == true && special[v[i].a - 1][v[i].b - 1] == true)
pos[v[i].a][v[i].b] = 2;
if(inside(Cell{v[i].a - 1, v[i].b + 1}) == true && special[v[i].a - 1][v[i].b + 1] == true)
pos[v[i].a][v[i].b] = 2;
int aux = pos[v[i].a][v[i].b];
if(inside(Cell{v[i].a + 1, v[i].b - 1}) == true && special[v[i].a + 1][v[i].b - 1] == true)
pos[v[i].a][v[i].b] = 0;
if(inside(Cell{v[i].a + 1, v[i].b + 1}) == true && special[v[i].a + 1][v[i].b + 1] == true)
pos[v[i].a][v[i].b] = 0;
if(aux != -1 && aux != pos[v[i].a][v[i].b])
{
cout << "No\n";
return 0;
}
}
for(int i = 1; i <= k; i++)
if(pos[v[i].a][v[i].b] != -1 && visited[v[i].a][v[i].b] == false)
{
if(dfs(v[i].a, v[i].b) == false)
{
cout << "No\n";
return 0;
}
}
int ans = 0;
for(int i = 1; i <= k; i++)
if(visited[v[i].a][v[i].b] == false)
{
cntu = cnte = 0;
mi = INT_MAX;
dfs1(v[i].a, v[i].b);
cnte /= 2;
if(cnte == cntu - 1)
ans -= mi;
else if(cnte > cntu)
{
cout << "No\n";
return 0;
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
if(special[i][j])
{
ans += ma[i][j];
continue;
}
bool ok = false;
for(int d = 0; d < 4; d++)
{
int i1 = i + da[d], j1 = j + db[d];
if(inside(Cell{i1, j1}) == false)
continue;
if(special[i1][j1] == true)
ok = true;
}
if(ok == true)
ans += ma[i][j];
}
cout << ans << "\n";
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
