38
查看原帖
38
1272259
cgxd楼主2024/4/30 14:44
#include<bits/stdc++.h>
#define y1 yone
#define unmap unordered_map
using namespace std;
int n, m, vis[305][305];
vector<string> v(1, string(305, '#'));
bitset<150> bs;
complex<int> c1, c2, place[150];
deque<complex<int>> dq;
unmap<int, unmap<int, complex<int>>> ma;
const complex<int> dir[] = {complex<int>(0, 1), complex<int>(1, 0), complex<int>(0, -1), complex<int>(-1, 0)};
void print(){
	for(complex<int> c: dq){
		int x1 = c.real();
		int y1 = c.imag();
		cout << c << vis[x1][y1] << ' ' << v[x1][y1];
	}cout << '\n';
}int main(){
	cin >> n >> m;
	bs.reset();
	for(int i = 1; i <= n; i++){
		string s(1, '#'), s1;
		cin >> s1;
		s += s1;
		s.push_back('#');
		v.push_back(s);
		for(unsigned j = 0; j < s.size(); j++){
			switch(s[j]){
				case '=':{
					c1 = complex<int>(i, j);
					break;
				}case '@':{
					c2 = complex<int>(i, j);
					break;
				}default:{
					if(isalpha(s[j])){
						if(bs[s[j]]){
							int x = place[s[j]].real();
							int y = place[s[j]].imag();
							ma[x][y] = complex<int>(i, j);
							ma[i][j] = complex<int>(x, y);
							//cout << i << j << x << y;
						}else{
							bs.set(s[j]);
							place[s[j]] = complex<int>(i, j);
						}
					}
				}
			}
		}
	}dq.push_back(c1);
	/*for(pair<int, unmap<int, complex<int>>> p: ma){
		for(pair<int, complex<int>> p1: p.second)
			cout << p.first << ' ' << p1.first << ' ' << p1.second << '\n';
	}*/int x = c1.real(), y = c1.imag();
	vis[x][y] = 1;
	//cout << c1 << c2 << '\n';
	while(dq.size()){
		complex<int> c3 = dq[0];
		int x = c3.real(), y = c3.imag();
		int k = vis[x][y];
		dq.pop_front();
		//cout << ma[x][y] << '\t';
		if(ma[x][y].real()){
			int x1 = ma[x][y].real();
			int y1 = ma[x][y].imag();
			if(!vis[x1][y1]){
				vis[x1][y1] = k;
				dq.push_front(ma[x][y]);
			}
		}for(complex<int> c: dir){
			complex<int> c4(c3 + c);
			int x1 = c4.real();
			int y1 = c4.imag();
			if(x1 < 0 or x1 >= n or y1 < 0 or y1 >= m)
				continue;
			if(vis[x1][y1] or v[x1][y1] == '#')
				continue;
			dq.push_back(c4);
			vis[x1][y1] = k + 1;
			if(dq.back() == c2){
				cout << k;
				return 0;
			}
		}//print();
	}return 0;
}
2024/4/30 14:44
加载中...