#101749 (C++11) No.367 ナイトの転身

提出ソース

結果

問題	No.367 ナイトの転身
ユーザー	IWK623
提出日時	2016-07-07 14:08:49
言語	C++11 (gcc 11.4.0)
結果	TLE
実行時間	-
コード長	5,689 bytes
コンパイル時間	1,264 ms
コンパイル使用メモリ	165,080 KB
実行使用メモリ	13,636 KB
最終ジャッジ日時	2024-10-12 23:02:38
合計ジャッジ時間	4,852 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 13,636 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	2 ms 6,820 KB
testcase_03	AC	1 ms 6,820 KB
testcase_04	AC	2 ms 6,816 KB
testcase_05	AC	2 ms 6,816 KB
testcase_06	AC	2 ms 6,816 KB
testcase_07	AC	2 ms 6,820 KB
testcase_08	AC	2 ms 6,820 KB
testcase_09	AC	1 ms 6,816 KB
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	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
	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));	
	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.cost = now.cost + 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.cost = now.cost + 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;
				ne.cost = now.cost + 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;*/
}

yukicoder

結果

テストケース

ソースコード