WA6求调
查看原帖
WA6求调
1036904
Eutopiax楼主2024/10/1 16:02
#include<bits/stdc++.h>

using namespace std;

struct NODE {
    int nm;
    int va;
};

int n;
int m;
vector<NODE> mp[550];
int st[550];

void bfs() {
    deque<int> dq;
    dq.push_front(1);
    st[1] = 1;
    int tm;
    while (!dq.empty()) {
        tm = dq.front();
        dq.pop_front();
        for (auto i: mp[tm]) {
            if (st[i.nm] == 0) {
                st[i.nm] = st[tm] + i.va;
                if (i.va == 0) {
                    dq.push_front(i.nm);
                } else {
                    dq.push_back(i.nm);
                }
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    if ((n + m) & 1) {
        printf("NO SOLUTION");
        return 0;
    }
    string s;
    int num;
    int num2;
    n++;
    m++;
    for (int i = 1; i <= n - 1; i++) {
        cin >> s;
        for (int j = 1; j <= m - 1; j++) {
            num = m * (i - 1) + j;
            num2 = num + m;
            if (s[j - 1] == '\\') {
                mp[num].push_back({num2 + 1, 0});
                mp[num2 + 1].push_back({num, 0});
                mp[num + 1].push_back({num2, 1});
                mp[num2].push_back({num + 1, 1});
            } else if (s[j - 1] == '/') {
                mp[num].push_back({num2 + 1, 1});
                mp[num2 + 1].push_back({num, 1});
                mp[num + 1].push_back({num2, 0});
                mp[num2].push_back({num + 1, 0});
            }
        }
        cout << "\n";
    }
    bfs();
    if (st[n * m] != 0) {
        printf("%d", st[n * m] - 1);
    } else {
        printf("NO SOLUTION");
    }
    return 0;
}

样例过了,自己造的小样例也过了,但是题目的小数据没过。

2024/10/1 16:02
加载中...