結果

問題 No.367 ナイトの転身
ユーザー IWK623IWK623
提出日時 2016-07-07 10:52:50
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 1 ms
6,820 KB
testcase_03 AC 1 ms
6,820 KB
testcase_04 AC 1 ms
6,816 KB
testcase_05 AC 1 ms
6,816 KB
testcase_06 AC 1 ms
6,816 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 1 ms
6,820 KB
testcase_09 WA -
testcase_10 TLE -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
}
0