結果

問題 No.3121 Prime Dance
ユーザー みどりむし🦠
提出日時 2025-04-20 19:39:39
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,765 bytes
コンパイル時間 4,060 ms
コンパイル使用メモリ 301,716 KB
実行使用メモリ 62,320 KB
最終ジャッジ日時 2025-04-20 19:40:30
合計ジャッジ時間 46,765 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

std::vector<int> primes(const int N )
{
    std::vector<bool> is_prime( N + 1 );
    for( int i = 0; i <= N; i++ )
    {
        is_prime[ i ] = true;
    }
    std::vector<int> P;
    for( int i = 2; i <= N; i++ )
    {
        if( is_prime[ i ] )
        {
            for( int j = 2 * i; j <= N; j += i )
            {
                is_prime[ j ] = false;
            }
            P.emplace_back( i );
        }
    }
    return P;
}

auto grid_bfs(vector< string > &s, char start, int gy, int gx, const string &wall = "#") {
  const int vx[] = {0, 1, 0, -1}, vy[] = {1, 0, -1, 0};
  vector< vector< int > > min_cost(s.size(), vector< int >(s[0].size(), -1));
  vector<vector<pair<int, int>>> cost(s.size(), vector<std::pair<int, int>>(s[0].size(), { -1, -1 }));
  queue< pair< int, int > > que;
  for(int i = 0; i < s.size(); i++) {
    for(int j = 0; j < s[i].size(); j++) {
      if(s[i][j] == start) {
        que.emplace(i, j);
        min_cost[i][j] = 0;
        cost[i][j] = { 0, 0 };
      }
    }
  }
  while(!que.empty()) {
    auto p = que.front();
    que.pop();
    for(int i = 0; i < 4; i++) {
      int ny = p.first + vy[i], nx = p.second + vx[i];
      if(nx < 0 || ny < 0 || nx >= s[0].size() || ny >= s.size()) continue;
      if(min_cost[ny][nx] != -1) continue;
      if(wall.find(s[ny][nx]) != string::npos) continue;
      min_cost[ny][nx] = min_cost[p.first][p.second] + 1;
      
      cost[ny][nx].first = cost[p.first][p.second].first + std::abs(vy[i]);
      cost[ny][nx].second = cost[p.first][p.second].second + std::abs(vx[i]);

      que.emplace(ny, nx);
    }
  }
  return cost[gy][gx];
}

int main() {
	const auto ps = primes(100000000);
	
	std::map<long, std::vector<int>> mp;
	for(int i : std::views::iota(1uz, ps.size())) {
		const int d = ps[i] - ps[i - 1];
		mp[d].push_back(ps[i - 1]);
	}
	
	// for(auto& [ k, v ] : mp) {
	// 	std::cerr << "{" << k << ", {";
	// 	for(auto x: v) std::cerr << x << ", ";
	// 	std::cerr << "} }, ";
	// }

	int h, w; std::cin >> h >> w;
	int sx, sy; std::cin >> sx >> sy; --sx, --sy;
	int gx, gy; std::cin >> gx >> gy; --gx, --gy;
	
	std::vector<std::string> grid(h);
	for(auto& row : grid) std::cin >> row;
	
	// std::cout << "test" << "\n";
	
	auto p = grid_bfs(grid, 'S', gx, gy);
	std::cerr << p.first << ", " << p.second << "\n";

	int dx = std::abs(sx - gx);
	int dy = std::abs(sy - gy);
	
	auto itrx = std::ranges::lower_bound(mp[dx], p.first);
	auto itry = std::ranges::lower_bound(mp[dy], p.second);
	
	if(
		itrx == mp[dx].end() || itry == mp[dy].end() ||
		p.first < 0 || p.second < 0
	) {
		std::cout << "-1\n";
		return 0;
	}
	
	std::cerr << *itrx << ", " << *itry << "\n";

	std::cout << 2 * (*itrx + *itry) + dx + dy << "\n";
}
0