求助
查看原帖
求助
1272259
cgxd楼主2024/4/5 18:32
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<string> v;
struct site{
	int x, y, a;
}bn, ed;
bool operator<(site p1, site p2){
	if(p1.x != p2.x)
		return p1.x < p2.x;
	return p1.y < p2.y;
}bool operator==(site p1, site p2){
	return p1.x == p2.x and p1.y == p2.y;
}int bfs(){
	int n = 0, k = 0;
	if(bn == ed)
		return 0;
	if(abs(bn.x - ed.x) == 1 and bn.y == ed.y or abs(bn.y - ed.y) == 1 and bn.x == ed.x)
		return 0;
	set<site> s;
	deque<site> d(1, bn);
	d.push_back(bn);
	while(d.size()){
		site s1 = {d[0].x + 1, d[0].y, d[0].a + 1};
		site s2 = {d[0].x, d[0].y + 1, d[0].a + 1};
		site s3 = {d[0].x - 1, d[0].y, d[0].a + 1};
		site s4 = {d[0].x, d[0].y - 1, d[0].a + 1};
		if(v[s1.x][s1.y] == 'O' and !s.count(s1)){
			d.push_back(s1);
			s.insert(s1);
		}if(v[s2.x][s2.y] == 'O' and !s.count(s2)){
			d.push_back(s2);
			s.insert(s2);
		}if(v[s3.x][s3.y] == 'O' and !s.count(s3)){
			d.push_back(s3);
			s.insert(s3);
		}if(v[s4.x][s4.y] == 'O' and !s.count(s4)){
			d.push_back(s4);
			s.insert(s4);
		}if(d[0].x == ed.x){
			string str(v[ed.x].substr(min(d[0].y, ed.y), abs(ed.y - d[0].y)));
			auto it = find(str.begin(), str.end(), 'X');
			if(it == str.end())
				return n;
		}if(d[0].y == ed.y){
			string str;
			for(int i = min(d[0].x, ed.x); i <= max(d[0].x, ed.x); i++){
				if(v[i][ed.y] == 'X')
					goto next;
			}return n;
		}if(k != d[0].a){
			k = d[0].a;
			n++;
		}next:
		d.pop_front();
	}return -1;
}int main(){
	cin >> n >> m;
	v.push_back(string(m, 'X'));
	while(n--){
		string s(1, 'X');
		string s1;
		cin >> s1;
		s += s1;
		s.push_back('X');
		v.push_back(s);
	}v.push_back(string(m, 'X'));
	do{
		cin >> bn.x >> bn.y >> ed.x >> ed.y;
		bn.a = 0;
		ed.a = 0;
		if(!bn.x)
			return 0;
		else{
			int k = bfs();
			if(k < 0)
				cout << "Poor Harry\n";
			else
				cout << k << '\n';
		} 
	}while(bn.x);
	return 0;
}
2024/4/5 18:32
加载中...