QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#348269 | #6739. Teleport | wtz2333 | WA | 36ms | 207764kb | C++17 | 2.9kb | 2024-03-09 17:37:47 | 2024-03-09 17:37:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 5100;
int dis[maxn][maxn][2];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};
struct node{
int x,y,opt;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n,k;
cin >> n >> k;
vector<string> s(n);
for(int i = 0;i < n;i ++) {
cin >> s[i];
}
memset(dis,0x3f,sizeof dis);
int inf = dis[0][0][0];
dis[0][0][0] = 0;
deque<node> q;
q.push_back({0,0,0});
// cerr << "!!!!\n";
while(!q.empty()) {
auto [x,y,opt] = q.front();
// cerr << x << " " << y << " " << opt << endl;
q.pop_front();
// cerr <<": asdfasd\n";
if(x == n - 1 && y == n - 1) {
cout << dis[x][y][opt] << endl;
return 0;
}
auto check = [&](int x,int y,int opt) -> bool {
if(x < 0 || x >= n) return false;
if(y < 0 || y >= n) return false;
if(s[x][y] == '*') return false;
// if(dis[x][y][opt] != inf) return false;
return true;
};
if(opt == 1) {
for(int i = 2;i < k;i += 2) {
int xx = x + (i / 2);
int yy = y + (i / 2);
if(check(xx,yy,0)) {
if(dis[xx][yy][0] < dis[x][y][opt]) break;
if(dis[xx][yy][0] == dis[x][y][opt])continue;
dis[xx][yy][0] = dis[x][y][opt];
q.push_front({xx,yy,0});
}
}
} else {
int xx = y + 1;
int yy = x;
if(check(xx,yy,1)) {
if(dis[xx][yy][1] <= dis[x][y][opt] + 1)continue;
dis[xx][yy][1] = dis[x][y][opt] + 1;
q.push_back({xx,yy,1});
}
for(int i = 2;i <= k;i += 2) {
int xx = x + (i / 2);
int yy = y + (i / 2);
if(check(xx,yy,0)) {
if(dis[xx][yy][0] < dis[x][y][opt] + 1) break;
if(dis[xx][yy][0] == dis[x][y][opt] + 1)continue;
dis[xx][yy][0] = dis[x][y][opt] + 1;
// cerr << "!!!! :" << xx << " " << yy << endl;
q.push_back({xx,yy,0});
}
}
}
// cerr <<": asdfasd\n";
for(int i = 0;i < 4;i ++) {
int xx = x + dx[i];
int yy = y + dy[i];
if(check(xx,yy,0)) {
if(dis[xx][yy][0] <= dis[x][y][opt] + 1)continue;
// cerr << xx << " " << yy << endl;
dis[xx][yy][0] = dis[x][y][opt] + 1;
q.push_back({xx,yy,0});
}
}
// cerr << "asdarewrew\n";
// cerr << "asdfgasd\n";
}
cout << -1 << endl;
return 0;
}
// 1 0 0 1 0 0
// 0 1 0 0 1 0
// 0 0 0 0 0 0
// 1 0 0 1 0 0
詳細信息
Test #1:
score: 100
Accepted
time: 7ms
memory: 206988kb
input:
3 2 .*. .*. ...
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 23ms
memory: 206808kb
input:
3 3 .*. .*. ...
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: -100
Wrong Answer
time: 36ms
memory: 207764kb
input:
961 4 ...*.*..*.....*.*..*..*..*.*.*.*.....*.....*....*..*...*....*.........*....*....*...*......*..*..*...*..*...*.....*...*...*.*.*.........**..**.......*.......*...*...*.*.*........*....*..*..*...*.....*.*......**.**..**...*..*.**.....*....*.*.*..*..*..*.*..*.*..*......*..*..*.*......*...*.*...*....
output:
547
result:
wrong answer 1st numbers differ - expected: '540', found: '547'