QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#348269#6739. Teleportwtz2333WA 36ms207764kbC++172.9kb2024-03-09 17:37:472024-03-09 17:37:49

Judging History

你现在查看的是最新测评结果

  • [2024-03-09 17:37:49]
  • 评测
  • 测评结果:WA
  • 用时:36ms
  • 内存:207764kb
  • [2024-03-09 17:37:47]
  • 提交

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'