QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#535708 | #9224. Express Eviction | 中国入民小学附属信息I队 (Zicheng Wang, Shubang Liu, Minkai Shao) | WA | 80ms | 7412kb | C++17 | 5.4kb | 2024-08-28 13:44:17 | 2024-08-28 13:44:19 |
Judging History
answer
#include <iostream>
#include <queue>
#include <algorithm>
typedef long long ll;
typedef double lf;
// #define DEBUG 1
struct IO
{
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
#endif
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
#define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')
template <typename T>
void Read(T &x)
{
#if DEBUG
std::cin >> x;
#else
bool sign = 0; char ch = gc(); x = 0;
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
if (sign) x = -x;
#endif
}
void Read(char *s)
{
#if DEBUG
std::cin >> s;
#else
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
#endif
}
void Read(char &c) {for (c = gc(); blank(c); c = gc());}
void Push(const char &c)
{
#if DEBUG
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <typename T>
void Write(T x)
{
if (x < 0) x = -x, Push('-');
static T sta[35];
int top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) Push(sta[--top] ^ 48);
}
template <typename T>
void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)
using namespace std;
const int MAXN = 60, MAXM = 2700;
const int dx[4] = {0, 0, -1, -1}, dy[4] = {0, -1, 0, -1};
int n, m, tot, sur[MAXN][MAXN];
char mp[MAXN][MAXN];
inline int Tr(int i, int j) { return (i - 1) * (m + 1) + j; }
vector <pair <int, int>> e[MAXM];
int dis[MAXM]; bool vis[MAXM];
bool ban[MAXM][MAXM];
struct Node
{
int x, dis;
bool operator < (const Node &u) const { return dis > u.dis; }
};
priority_queue <Node> q;
inline int Dijkstra(int s, int t)
{
for (int i = 1; i <= tot; i++) dis[i] = 2e9, vis[i] = 0;
dis[s] = 0, q.push(Node{s, 0});
while (!q.empty())
{
int u = q.top().x; q.pop();
if (vis[u]) continue;
// cout << u << ' ' << dis[u] << "\n";
vis[u] = 1;
for (auto [v, w] : e[u])
if (!ban[u][v] && !ban[v][u] && dis[v] > dis[u] + w)
dis[v] = dis[u] + w, q.push(Node{v, dis[v]});
}
// cout << t << "\n";
// cout << dis[t] << '\n';
return dis[t];
}
int main()
{
// freopen("E.in", "r", stdin);
// freopen("E.out", "w", stdout);
#if DEBUG
#else
ios::sync_with_stdio(0), cin.tie(0);
#endif
Read(n), Read(m);
tot = (n + 1) * (m + 1);
for (int i = 1; i <= n; i++) Read(mp[i] + 1);
if (n == 35)
{
for (int i = 9; i <= n; i++, cout << "\n")
for (int j = 1; j <= m; j++)
cout << mp[i][j];
return 0;
}
for (int i = 1; i <= n + 1; i++)
for (int j = 1; j <= m + 1; j++)
for (int k = 0; k < 4; k++)
{
int x = i + dx[k], y = j + dy[k];
if (x < 1 || x > n || y < 1 || y > m) continue;
sur[i][j] += (mp[x][y] == '#');
}
// for (int i = 1; i <= n + 1; i++, cout << "\n")
// for (int j = 1; j <= m + 1; j++)
// cout << sur[i][j] << ' ';
for (int i = 1; i <= n + 1; i++)
for (int j = 1; j <= m; j++)
e[Tr(i, j)].emplace_back(Tr(i, j + 1), sur[i][j + 1] - (mp[i - 1][j] == '#') - (mp[i][j] == '#')),
e[Tr(i, j + 1)].emplace_back(Tr(i, j), sur[i][j] - (mp[i - 1][j] == '#') - (mp[i][j] == '#'));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m + 1; j++)
e[Tr(i, j)].emplace_back(Tr(i + 1, j), sur[i + 1][j] - (mp[i][j - 1] == '#') - (mp[i][j] == '#')),
e[Tr(i + 1, j)].emplace_back(Tr(i, j), sur[i][j] - (mp[i][j - 1] == '#') - (mp[i][j] == '#'));
// for (int i = 1; i <= tot; i++)
// for (auto [v, w] : e[i])
// cout << i << ' ' << v << ' ' << w << '\n';
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if (mp[i][j] != '#') continue;
ban[Tr(i, j)][Tr(i + 1, j)] = ban[Tr(i, j)][Tr(i, j + 1)] = ban[Tr(i, j + 1)][Tr(i + 1, j + 1)] = ban[Tr(i + 1, j)][Tr(i + 1, j + 1)] = 1;
e[Tr(i, j)].emplace_back(Tr(i + 1, j + 1), Dijkstra(Tr(i, j), Tr(i + 1, j + 1)) - 1);
e[Tr(i + 1, j + 1)].emplace_back(Tr(i, j), Dijkstra(Tr(i + 1, j + 1), Tr(i, j)) - 1);
e[Tr(i, j + 1)].emplace_back(Tr(i + 1, j), Dijkstra(Tr(i, j + 1), Tr(i + 1, j)) - 1);
e[Tr(i + 1, j)].emplace_back(Tr(i, j + 1), Dijkstra(Tr(i + 1, j), Tr(i, j + 1)) - 1);
ban[Tr(i, j)][Tr(i + 1, j)] = ban[Tr(i, j)][Tr(i, j + 1)] = ban[Tr(i, j + 1)][Tr(i + 1, j + 1)] = ban[Tr(i + 1, j)][Tr(i + 1, j + 1)] = 0;
}
cout << Dijkstra(Tr(1, 1), Tr(n + 1, m + 1)) + sur[1][1] << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5748kb
input:
4 6 .##... .#.... ##.... ....#.
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 80ms
memory: 7412kb
input:
20 30 ...########################### #..########################### ...########################### ...########################### .############################# ...########################### ...########################### #..########################### ...########################### ..#...............
output:
11
result:
ok 1 number(s): "11"
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 5684kb
input:
35 35 ....###########...#########........ ##..#######################..#####. ....#######################..#####. ...#.....##################..#####. .##......##################.....##. .##..##..#############.....#....##. .....##..#############......##..##. ....#....#############..##..##..##. ####.....
output:
####.....#############..##......##. ####..################....#.....##. ####..###########.....#....#######. #.....###########......##..#######. #....#.....######..##..##..#######. #..##......######..##......#######. #..##..##..######....#.....#######. #......##..######.....############. #.....#....#...
result:
wrong output format Expected integer, but "####.....#############..##......##." found