题解 | ACM中的AC题

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

int n, m , s_x, s_y;
char c[2005][2005];
int dist[2005][2005][2];
int direction[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; 

//int vis[11][11][10005];
//struct status {
//	int x;
//	int y;
//	int cost;
//	int modVal;
//};

struct status {
	int x;
	int y;
	int flag;
};

//C++大小写敏感，且可以直接const int == int会有隐式转换
const int MIN_VAL = 10000000;
//1.将两个点变成一个点的约束
//2.引入flag这个维度状态
//3.状态之间是怎么转换的
int main() {
    cin >> n >> m >> s_x >> s_y;
//    p--;
	for (int i = 1; i <= n; i++)  {
		for (int j = 1; j <= m; j++) {
			cin >> c[i][j];
		}
	}
	memset(dist, 0xFF, sizeof(dist));
	queue<status> q;
	status st;
	st.x = s_x;
	st.y = s_y;
	st.flag = 0;
	dist[st.x][st.y][st.flag] = 0;
	q.push(st);
	int minVal = MIN_VAL;
	while (!q.empty()) {
		status s = q.front();
		q.pop();
		if (s.flag && c[s.x][s.y] == '@') {
			minVal = min(minVal, dist[s.x][s.y][s.flag]);
		}
		for (int i = 0; i < 4; i++) {
			int x = s.x + direction[i][0];
			int y = s.y + direction[i][1];
			//求x, y关于s_x, s_y的对称点
			int x_2 = 2 * s_x - x;
			int y_2 = 2 * s_y - y;
			
		  	//falg = 1之后的对称点不受限制
			if (x <= n && x > 0 && y <= m && y > 0 && c[x][y] != '#' && (s.flag || (x_2 <= n && x_2 > 0 && y_2 <= m && y_2 > 0 && c[x_2][y_2] != '#' && !(c[x_2][y_2] != '@' && c[x][y] == '@')))) {
				//根据之前点位的flag赋值 
				int new_flag = s.flag;
				if (!new_flag) {
					new_flag = c[x_2][y_2] == '@' ? 1 : 0; 
				}
				//没访问过更新，加入队列扩展 			
				if (dist[x][y][new_flag] < 0) {
					status new_s;
					new_s.x = x;
					new_s.y = y;
					new_s.flag = new_flag;
					dist[x][y][new_flag] = dist[s.x][s.y][s.flag] + 1;
					q.push(new_s);
				}
			}
		}
	}
	cout << (minVal == MIN_VAL ? -1 : minVal) << endl;
}