题目描述
题目描述
众所周知，小埋是一个准时完成作业的优秀同学。但是小埋在做梦写作业，遇到一个迷宫，上面指示描述作业就在迷宫之中，你必须从迷宫中找到这个作业，然后完成它。对于小埋同学来说，写作业是很简单的一件事情，但是从迷宫中找到作业却很困难，现在请你帮小埋从迷宫中找到该作业。
小埋从 （1,1）（1,1） 开始，每秒可以向上下左右某一方向走2的次方步，请你帮助小埋用最少的时间找到该作业。
输入格式
第一行两个整数
n
，
m
n，m。
接下来
n
n 行，每行
m
m 个字符,$ 或者 . 表示可走的空地，X 表示障碍，#表示作业。（保证只有一个作业）
输出格式
小埋到达作业最短耗时。如果没有解输出-1。
对着回放看了好几遍了没发现问题
#include<bits/stdc++.h>
using namespace std;
int n, m, sum[1000 + 20][1000 + 20], dist[1000 + 20][1000 + 20];
int d[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
string s[1000 + 20];
int get(int x1, int y_1, int x2, int y2) {
if (x1 > x2) {
swap(x1, x2);
}
if (y_1 > y2) {
swap(y_1, y2);
}
return sum[x2][y2] - sum[x2][y_1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y_1 - 1];
}
queue<pair<int, int> >q;
void bfs() {
memset(dist, 0x3f, sizeof(dist));
q.push({1, 1});
dist[1][1] = 0;
while (!q.empty()) {
auto t = q.front();
q.pop();
int x = t.first;
int y = t.second;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 10; j++) {
int dx = x + d[i][0] * (1 << j), dy = y + d[i][1] * (1 << j);
if (dx < 1 || dx > n || dy < 1 || dy > m) {
break;
}
if (get(x, y, dx, dy)) {
break;
}
if (dist[dx][dy] > dist[x][y] + 1) {
dist[dx][dy] = dist[x][y] + 1;
if (s[dx][dy] == '#') {
cout << dist[dx][dy] << endl;
return ;
}
}
q.push({dx, dy});
}
}
}
cout<<-1<<endl;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> s[i];
s[i] = " " + s[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (s[i][j] == 'X');
}
}
bfs();
return 0;
}