結果

問題 No.367 ナイトの転身
ユーザー IWK623
提出日時 2016-07-07 10:52:50
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 4,070 bytes
コンパイル時間 1,466 ms
コンパイル使用メモリ 163,572 KB
実行使用メモリ 13,636 KB
最終ジャッジ日時 2024-10-12 23:00:42
合計ジャッジ時間 4,870 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 2 TLE * 1 -- * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘Node NodeList::getNode(int)’:
main.cpp:54:17: warning: control reaches end of non-void function [-Wreturn-type]
   54 |                 }
      |                 ^

ソースコード

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.
        void push_data(Node n){
            datas.push_back(n);
        }
        void remove(vector<Node>::iterator iterator){
            datas.erase(iterator);
        }
        int getSize(){
            return datas.size();
        }
        Node getNode(int id){
            vector<Node>::iterator iterator = datas.begin();
            while (iterator != datas.end()){
                if(id == (*iterator).id){
                    return *iterator;
                }
                iterator++;
            };
        }
        Node getMinCost(){
            vector<Node>::iterator iterator = datas.begin(),result = datas.begin();
            int min = (*iterator).cost;
            while (iterator != datas.end()){
                if(min > (*iterator).cost){
                    result = iterator;
                }
                iterator++;
            }
            remove(result);
            return *result;
        }
        vector<Node>::iterator find(int x,int y){
            vector<Node>::iterator iterator = datas.begin();
            while (iterator != datas.end()){
                if((*iterator).x == x and (*iterator).y == y){
                    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;
    char map_char[n1][n2];
    Node Start = Node(0,0,0,false,0,-1,1);
    Node Goal = Node(0,0,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;  
    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();//計算中の中で一番コストの低いノードを取り出す。（同時に削除される。）
        closeMap.push_data(now);//計算済みのほうへ移動。
        //cout << now.id << " (" << now.x+1 << "," << now.y+1 << ") " <<  now.pre  << " " << now.type << endl;      
        if(now.x == Goal.x && now.y == Goal.y)break;
        
        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];
            //cout << now.id << " (" << cy+1 << "," << cx+1 << ")" << endl;
            if((cx < 0) or (cx > (n1 - 1)) or (cy < 0) or (cy > (n2 - 1)))continue;
            vector<Node>::iterator openFind = openMap.find(cx,cy);
            vector<Node>::iterator closeFind = closeMap.find(cx,cy);
            if(openMap.isFind(openFind)){
            }else if(closeMap.isFind(closeFind)){
            }else{
                Node ne = Node(cx,cy,now.cost+1,false,pid,now.id,
                    ChangeMode(now.type,(map_char[cx][cy] == 'R' ? true : false)));
                pid++;
                openMap.push_data(ne);
            }
        }
    }
    int c = 0;
    //cout << endl;
    while(true){
        if(now.id < 0)break;
        //cout << now.id << " (" << now.y+1 << "," << now.x+1 << ") " <<  now.pre << endl;
        now = closeMap.getNode(now.pre);
        c++;
    }
    cout << c << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0