AOJ1189 素数洞穴

解法

---

DFS。途中で1000000とかセグフォで逝っちゃうんじゃね？って思いながら組んでいったが、
案の定逝ってしまったのでBFSに書き直して勝ったと思っていたら負けていた。
素数配列の大きさが100001で一桁足りないじゃんって気付くまで時間がかかった。
洞穴のマップを最初に最大値まで求めて作っておく。あと素数も。
これはdy[],dx[]のアレを考慮してやって、進行方向の左側に数字が入ってなかったら曲がろうという方針。
某副部長兼キチガイが提案してくれたので頭いいなと思った。この実装はすぐできた。
ちゃんと答えまで出たらmax_costをint型からpairにして最後に通った素数の判定を感で付け加えた。

ソース

---

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
#define fr first
#define sc second
const int dy[] = { 0, -1, 0, 1}, dx[] = { 1, 0, -1, 0}; //右上左下
typedef pair< int , int > Pt;
int m,n,mas[1005][1005],hw = 1000;
Pt buff[1000001],max_cost[1005][1005];
bool prime[1000001];
void Prime_set(){
  prime[1] = true;
  for(int i = 2 ; i * i < 1000001 ; i++ ){
    if(!prime[i]) for(int j = i + i ; j < 1000001 ; j += i ) prime[j] = true;
  }
}
bool isover(int y,int x){
  return x < 0 || !mas[y][x] || mas[y][x] > m;
}
void make_map(){
  fill_n(*mas,1005*1005,0);
  int cnt = 1,muki = 3;
  Pt now = Pt( hw / 2,  hw / 2),St;
  while(cnt <= 1000000){
    buff[cnt] = Pt(now.fr,now.sc);
    mas[now.fr][now.sc] = cnt++;
    Pt magaru = Pt( now.fr + dy[(muki + 1) % 4], now.sc + dx[(muki + 1) % 4]);
    if(!mas[magaru.fr][magaru.sc]) muki = (muki + 1) % 4, now = magaru;
    else now.fr += dy[muki], now.sc += dx[muki];
  }
}
Pt dfs(Pt now){
  if(max_cost[now.fr][now.sc] != Pt(-1,-1)) return max_cost[now.fr][now.sc];
  Pt ret = Pt();
  for(int i = 0 ; i < 3 ; i++ ){
    int nx = now.sc + dx[i];
    if(!isover(now.fr+1,nx)) ret = max(ret,dfs(Pt(now.fr+1,nx)));
  }
  if(!ret.sc && !prime[mas[now.fr][now.sc]]) ret.sc = mas[now.fr][now.sc];
  return max_cost[now.fr][now.sc] = Pt(ret.fr+!prime[mas[now.fr][now.sc]],ret.sc);
}
int main(){
  Prime_set();
  make_map();
  while(cin >> m >> n , m){
    fill_n(*max_cost,1005*1005,Pt(-1,-1));
    Pt ans = dfs(buff[n]);
    cout << ans.fr << " " << ans.sc << endl;
  }
}