QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#270366#7751. Palindrome Pathucup-team859#WA 1ms9812kbC++144.7kb2023-11-30 19:55:272023-11-30 19:55:27

Judging History

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

  • [2023-11-30 19:55:27]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:9812kb
  • [2023-11-30 19:55:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;

using ll = long long;
using ull = unsigned long long;

string to_string(const string &s) {
  return '"' + s + '"';
}

string to_string(bool b) {
  return b ? "true" : "false";
}

template <typename A, typename B>
string to_string(const pair<A, B> &p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename T>
string to_string(const T &v) {
  string s = "{";
  bool first = true;
  for (const auto &it : v) {
    if (!first)
      s += ", ";
    else
      first = false;
    s += to_string(it);
  }
  return s += "}";
}

void debug_out() {
  cerr << endl;
}

template <typename T, typename... Args>
void debug_out(const T &first, const Args&... rest) {
  cerr << to_string(first) << " ";
  debug_out(rest...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

auto startTime = high_resolution_clock::now();
int get_time() {
  auto stopTime = chrono::high_resolution_clock::now();
  auto duration = duration_cast<milliseconds>(stopTime - startTime);
  return duration.count(); // in ms
}

struct usu {
  int x, y, x2, y2;
};

int n, m;
usu tt[31][31][31][31];
int marked[31][31];
int viz[31][31][31][31];
int a[31][31];

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

const int dx2[] = {1, -1, 0, 0};
const int dy2[] = {0, 0, 1, -1};

const int rk[] = {1, 0, 3, 2};

const char ch[] = {'U', 'D', 'L', 'R'};

inline bool in_bounds(int i, int j) {
  return i >= 1 && i <= n && j >= 1 && j <= m && a[i][j];
}

vector<int> ordk;
vector<int> dfp;
int nr = 0;
void dfs(int x, int y) {
  shuffle(ordk.begin(), ordk.end(), rng);
  for (auto k : ordk) {
    int i = dx[k] + x;
    int j = dy[k] + y;

    if (in_bounds(i, j) && marked[i][j] != nr) {
      marked[i][j] = nr;
      dfp.push_back(k);
      dfs(i, j);
      dfp.push_back(rk[k]);
    }
  }
}

void print_path(int x, int y, int x2, int y2) {
  string ans;

  while (viz[x][y][x2][y2] != -1) {
    int k = viz[x][y][x2][y2] - 1;
    ans.push_back(ch[k]);

    auto tmp = tt[x][y][x2][y2];
    x = tmp.x;
    y = tmp.y;
    x2 = tmp.x2;
    y2 = tmp.y2;
  }

  reverse(ans.begin(), ans.end());

  string str;
  for (auto it : dfp)
    str.push_back(ch[it]);

  for (auto it = dfp.rbegin(); it != dfp.rend(); ++it)
    str.push_back(ch[*it]);

  string sol = ans + str;
  reverse(ans.begin(), ans.end());
  sol += ans;

  for (auto it : sol)
    cout << it;
  cout << '\n';
}

void solve() {
  ordk = {0, 1, 2, 3};
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    string s;
    cin >> s;
    for (int j = 1; j <= m; ++j) {
      a[i][j] = s[j - 1] - '0';
    }
  }

  int x, y, x2, y2;
  cin >> x >> y >> x2 >> y2;
  queue<usu> q;
  viz[x][y][x2][y2] = -1;
  q.push({x, y, x2, y2});

  int sx = -1, sy = -1;
  while (!q.empty()) {
    x = q.front().x;
    y = q.front().y;
    x2 = q.front().x2;
    y2 = q.front().y2;
    q.pop();

    for (int k = 0; k < 4; ++k) {
      int i = dx[k] + x;
      int j = dy[k] + y;

      int i2 = dx2[k] + x2;
      int j2 = dy2[k] + y2;

      if (!in_bounds(i, j)) {
        i -= dx[k];
        j -= dy[k];
      }

      if (!in_bounds(i2, j2)) {
        i2 -= dx2[k];
        j2 -= dy2[k];
      }

      if (!viz[i][j][i2][j2]) {
        tt[i][j][i2][j2] = {x, y, x2, y2};
        viz[i][j][i2][j2] = k + 1;
        q.push({i, j, i2, j2});
      }

      i2 = dx[k] + x2;
      j2 = dy[k] + y2;

      if (!in_bounds(i2, j2)) {
        i2 = x2;
        j2 = y2;
        if (!viz[i][j][i2][j2]) {
          tt[i][j][i2][j2] = {x, y, x2, y2};
          viz[i][j][i2][j2] = k + 1;
          q.push({i, j, i2, j2});
        }
      }
    }
  }

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      ++nr;
      dfp.clear();
      dfs(i, j);

      int i2 = i, j2 = j;

      for (auto it : dfp) {
        i2 += dx[it];
        j2 += dy[it];
        if (!in_bounds(i2, j2)) {
          i2 -= dx[it];
          j2 -= dy[it];
        }
      }
      
      for (auto it = dfp.rbegin(); it != dfp.rend(); ++it) {
        i2 += dx[*it];
        j2 += dy[*it];
        if (!in_bounds(i2, j2)) {
          i2 -= dx[*it];
          j2 -= dy[*it];
        }
      }

      if (viz[i][j][i2][j2]) {
        print_path(i, j, i2, j2);
        return;
      }
    }
  }

  cout << "-1\n";
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  int t = 1;
//  cin >> t;
  while (t--)
    solve();

  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 9812kb

input:

2 2
11
11
1 1 2 2

output:

RLDRLURLLRULRDLR

result:

ok Valid Solution (Length = 16).

Test #2:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

1 1
1
1 1 1 1

output:



result:

ok Valid Solution (Length = 0).

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 7904kb

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

UUULLRRRDDDDLULDLUUURRDLRULLUDDDDRURDRUUUULLLLLLUUUURDRURDDDDULLURLDRRUUULDLULDDDDRRRLLUUU

result:

wrong answer End Point Is (2,2), Not (er = 4, ec = 2)