結果

問題 No.3121 Prime Dance
ユーザー 入野拳樹
提出日時 2025-04-20 16:11:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,972 bytes
コンパイル時間 1,628 ms
コンパイル使用メモリ 130,524 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-20 16:11:24
合計ジャッジ時間 2,288 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <bitset>
#include <tuple>
#include <map>
#include <functional>

#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define orep(i,n) for(ll i=1;i<=(n);i++)

#define nfor(i,s,n) for(ll i=(s);i<(n);i++)
#define dfor(i,s,n) for(ll i=(s)-1;i>=n;i--)
#define INF 9e18//9223372036854775807

#define all(a)  a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)

#define pb push_back
#define pob pop_back

#define vc vector

#define YES cout << "Yes" << endl;
#define NO cout << "No" << endl;
#define YN {cout << "Yes" << endl;}else{cout << "No" << endl;}
#define dame cout << -1 << endl;

#define vc_unique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define vc_rotate(v) rotate(v.begin(), v.begin()+1, v.end())

#define pop_cnt(s) ll(popcount(uint64_t(s)))
#define next_p(v) next_permutation(v.begin(),v.end())

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif

using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll,ll>;
using vvl = vector<vector<ll>>;
using vl = vector<ll>;
using Graph = vector<vector<ll>>;

template<class T> using pq = priority_queue<T,vc<T>,less<T>>;
template<class T> using pq_g = priority_queue<T,vc<T>,greater<T>>;

vl dx = {1,-1,0,0};//vl dx = {1,1,0,-1,-1,-1,0,1};
vl dy = {0,0,1,-1};//vl dy = {0,1,1,1,0,-1,-1,-1};

bool out_grid(ll i, ll j, ll h, ll w){//trueならcontinueする
	return(!(0 <= i && i < h && 0 <= j && j<w));
}

void print(ld x){printf("%.20Lf\n", x);}

//////////////////////////////////////////////////////////////////

int main(){

	vc<ll>sosu(20001,0);
	sosu[1] = 1;
	nfor(i,2,450){
		if(sosu[i] != 0)continue;
		else{
			ll j = 2;
			while(j*i < 20001){
				sosu[j*i]++;
				j++;
			}
		}
	}


	ll H,W;
	cin >> H >> W;
	ll Sx,Sy;
	ll Gx,Gy;
	cin >> Sx >> Sy;
	cin >> Gx >> Gy;
	Sx--;Sy--;
	Gx--;Gy--;

	vector<vector<char>> G(H,vc<char>(W));
	rep(i,H)rep(j,W){
		cin >> G[i][j];
	}

	vvl dist(H,vl(W,-1));
	vector<vector<pll>> pre(H,vc<pll>(W,{-1,-1}));
	
	queue<pll> que;

	que.push({Sx,Sy});

	dist[Sx][Sy] = 0;

	bool F = false;

	while(!que.empty() && !F){
		ll x = que.front().fi;
		ll y = que.front().se;
		que.pop();
		rep(i,4){
			ll nx = x + dx[i];
			ll ny = y + dy[i];
			if(nx >= H || ny >= W || nx < 0 || ny < 0)continue;
			if(G[nx][ny] == '#')continue;
			if(dist[nx][ny] != -1)continue;
			dist[nx][ny] = dist[x][y] + 1;
			pre[nx][ny] = {x,y};
			if(nx == Gx && ny == Gy){
				F = true;
				break;
			}else{
				que.push({nx,ny});
			}
		}
	}

	

	ll x = Gx;ll y = Gy;

	ll A = 0;
	ll B = 0;
	ll C = 0;
	ll D = 0;
	bool tate = false;
	bool yoko = false;

	while(!(x == Sx && y == Sy)){
		rep(i,4){
			ll nx = x + dx[i];
			ll ny = y + dy[i];
			if(nx >= H || ny >= W || nx < 0 || ny < 0)continue;
			if(G[nx][ny] != '#'){
				if(i == 0 || i == 1){
					tate = true;
				}else{
					yoko = true;
				}
			}
		}

		ll prex = pre[x][y].fi;
		ll prey = pre[x][y].se;

		if(x - prex == 1)A++;
		if(x - prex == -1)B++;
		if(y - prey == 1)C++;
		if(y - prey == -1)D++;

		x = prex;y = prey;
	}
	rep(i,4){
		ll nx = x + dx[i];
		ll ny = y + dy[i];
		if(nx >= H || ny >= W || nx < 0 || ny < 0)continue;
		if(G[nx][ny] != '#'){
			if(i == 0 || i == 1){
				tate = true;
			}else{
				yoko = true;
			}
		}
	}

	bool mAB = false;
	bool mCD = false;

	if(!(tate && yoko))dame
	else{
		if(A == 0 || B == 0){
			A++;B++;
		}
		while(A<20000 && B<20000){
			if(sosu[A] == 0 && sosu[B] == 0){
				mAB = true;
				break;
			}
			else{
				A++;B++;
			}
		}

		if(C == 0 || D == 0){
			C++;D++;
		}
		while(C<20000 && D<20000){
			if(sosu[C] == 0 && sosu[D] == 0){
				mCD = true;
				break;
			}
			else{
				C++;D++;
			}
		}
		if(mAB && mCD)cout << A+B+C+D << endl;
		else dame
	}
}
0