結果

問題 No.367 ナイトの転身
ユーザー IWK623
提出日時 2016-07-07 13:47:46
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 5,645 bytes
コンパイル時間 1,523 ms
コンパイル使用メモリ 165,372 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-12 23:02:27
合計ジャッジ時間 2,131 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
class Node{
    public:
        int x,y,cost;
        bool isWall,isGoal;
        int id;
        int pre;
        int type;
    public:
        Node(int nx,int ny,int ncost,bool ng,int nid,int npre,int ntype){
            x = nx;//X
            y = ny;//Y
            cost = ncost;//このノードまでのコスト
            isGoal = ng;//ゴールかどうか
            id = nid;//自身のID
            pre = npre;//ひとつ前のノードのID
            type = ntype;//1 or 2 (1は♞２はミニビショップ)
        }
};
class NodeList{
    public:
        // iteratorをtypedefする
        typedef vector<Node>::iterator iterator;
        typedef vector<Node>::const_iterator const_iterator;
        // begin, end
        iterator begin(){ return datas.begin(); }
        const_iterator begin() const { return datas.begin(); }
        iterator end(){ return datas.end(); }
        const_iterator end() const { return datas.end(); }
    public:
        vector<Node> datas; // OpenListまたはCloseList.
        vector<Node>::iterator result;
        void push_data(Node n){
            datas.push_back(n);
        }
        void remove(vector<Node>::iterator iterator){
            datas.erase(iterator);
        }
        int getSize(){
            return datas.size();
        }
        vector<Node>::iterator getNode(int id){
            vector<Node>::iterator iterator = datas.begin();
            while (iterator != datas.end()){
                if(id == (*iterator).id){
                    return iterator;
                }
                iterator++;
            };
            return datas.end();
        }
        Node getMinCost(){
            vector<Node>::iterator iterator = datas.begin();
            result = datas.begin();
            int min = (*iterator).cost;
            while (iterator != datas.end()){
                //cout << min << " <=> " << (*iterator).cost << endl;
                if(min > (*iterator).cost){
                    result = iterator;
                    min = (*iterator).cost;
                }
                iterator++;
            }
            //remove(result);
            return *result;
        }
        vector<Node>::iterator find(int x,int y,int type){
            vector<Node>::iterator iterator = datas.begin();
            while (iterator != datas.end()){
                if((*iterator).x == x and (*iterator).y == y and (*iterator).type == type){
                    return iterator;
                }
                iterator++;
            }
            return datas.end(); 
        }
        bool isFind(vector<Node>::iterator it){
            return datas.end() == it ? false : true;
        }
};
int ChangeMode(int type,bool red){
    if(!red){
        return type;
    }else{
        return type == 1 ? 2 : 1;
    }
}
int main(){
    int n1,n2;
    cin >> n1 >> n2;
    //n1 = 500;n2 = 500;
    char map_char[n1][n2];
    Node Start = Node(0,0,0,false,0,-1,1);
    Node Goal = Node(499,499,0,true,0,-1,0);
    for(int i = 0;i < n1;i++){
        cin >> map_char[i];
    }
    for(int i = 0;i < n1;i++){
        for(int j = 0;j < n2;j++){
            if(map_char[i][j] == 'S'){
                Start.x = i;
                Start.y = j;
            }else if(map_char[i][j] == 'G'){
                Goal.x = i;
                Goal.y = j;
            }
        }
    }
    Node now = Node(0,0,0,0,0,0,0);
    int pid = 0;
    Start.id = -1;
    Start.cost = sqrt(pow((Goal.x - Start.x),2) + pow((Goal.y - Start.y),2));   
    //cout << Start.cost << endl;
    NodeList openMap;
    NodeList closeMap;
    openMap.push_data(Start);
    int move[2][8][2] = {{{1,2},{-1,2},{-1,-2},{1,-2},{2,1},{-2,1},{-2,-1},{2,-1}},
                        {{1,1},{1,-1},{-1,-1},{-1,1}}};
    int cx,cy;
    while(true){
        if(openMap.getSize() <= 0){
            cout << -1 << endl;
            return 0;
        }
        now = openMap.getMinCost();//計算中の中で一番コストの低いノードを取り出す。（同時に削除される。）
        openMap.remove(openMap.result);
        closeMap.push_data(now);//計算済みのほうへ移動。
        //cout << now.id << ":" << now.pre << ":" << now.type << " (" << now.x + 1 << "," << now.y + 1<< ")" << now.cost << endl;       
        if(now.x == Goal.x && now.y == Goal.y){
            cout << now.cost << endl;
            return 0;
        }
        for(int i = 0;(now.type == 1 and i < 8) or (now.type == 2 and i < 4);i++){
            cx = now.x + move[now.type - 1][i][0];
            cy = now.y + move[now.type - 1][i][1];
            if((cx < 0) or (cx > (n1 - 1)) or (cy < 0) or (cy > (n2 - 1)))continue;
            vector<Node>::iterator openFind = openMap.find(cx,cy,ChangeMode(now.type,(map_char[cx][cy] == 'R' ? true : false)));
            vector<Node>::iterator closeFind = closeMap.find(cx,cy,ChangeMode(now.type,(map_char[cx][cy] == 'R' ? true : false)));
            int fd = sqrt(pow((Goal.x - now.x),2) + pow((Goal.y - now.y),2));
            if(openMap.isFind(openFind)){
                Node ne = *openFind;
                if(ne.cost > now.cost+1){
                    ne.cost = (now.cost - fd) + (sqrt(pow((Goal.x - ne.x),2) + pow((Goal.y - ne.y),2))) + 1;
                    ne.pre = now.id;
                    ne.type = ChangeMode(now.type,(map_char[cx][cy] == 'R' ? true : false));
                }
            }else if(closeMap.isFind(closeFind)){
                Node ne = *closeFind;
                if(ne.cost > now.cost+1){
                    closeMap.remove(closeFind);
                    ne.cost = (now.cost - fd) + (sqrt(pow((Goal.x - ne.x),2) + pow((Goal.y - ne.y),2))) + 1;
                    ne.pre = now.id;
                    ne.type = ChangeMode(now.type,(map_char[cx][cy] == 'R' ? true : false));    
                    openMap.push_data(ne);
                }
            }else{
                Node ne = Node(cx,cy,now.cost+1,false,pid,now.id,
                    ChangeMode(now.type,(map_char[cx][cy] == 'R' ? true : false)));
                ne.cost = (now.cost - fd) + (sqrt(pow((Goal.x - ne.x),2) + pow((Goal.y - ne.y),2))) + 1;
                pid++;
                openMap.push_data(ne);
                //cout << " > " << ne.id << ":" << ne.pre << ":" << ne.type << " (" << ne.x + 1 << "," << ne.y + 1<< ")" << ne.cost << endl;
            }
        }
    }
    /*int c = 0;
    cout << "to Path... "<< endl;
    while(true){
        if(now.id < 0)break;
        cout << "<" << now.id << "," << now.pre << ">";
        vector<Node>::iterator path = closeMap.getNode(now.pre);
        if(!closeMap.isFind(path)){
            cout << endl << now.id << " (" << now.y+1 << "," << now.x+1 << ") " <<  now.pre << endl;
            vector<Node>::iterator path = openMap.getNode(now.pre);     
        }
        now = *path;
        c++;
    }
    cout << endl;
    cout << c << endl;*/
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0