大意不再赘述。
思路:比较简单的广搜,给定8个方向,只要现在广搜的方向与之前所在的点的风的方向不同的话,消耗量加1即可。可以用优先队列每次取出时间最少的那个点,用TIME数组判状态,如简单的判是否走过的话,会TLE,而用TIME数组保证最先到达终点的点一定是消耗量最小的。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> #include <queue> using namespace std; const int MAXN = 1010; const int INF = 0x3f3f3f3f; const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}; const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1}; int n, m; struct node { int x, y; int step; bool operator < (const node &a) const { return a.step < step; } }; char maze[MAXN][MAXN]; int TIME[MAXN][MAXN]; int check(int x, int y) { if(x >= 1 && x <= n && y >= 1 && y <= m) return 1; return 0; } priority_queue<node> Q; void init() { for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { TIME[i][j] = INF; } } } void bfs(int bx, int by, int ex, int ey) { while(!Q.empty()) Q.pop(); node cur, next; cur.x = bx, cur.y = by, cur.step = 0; TIME[bx][by] = 0; Q.push(cur); while(!Q.empty()) { cur = Q.top(); Q.pop(); if(cur.x == ex && cur.y == ey) return ; for(int i = 0; i < 8; i++) { next = cur; next.x += dx[i], next.y += dy[i]; if(i != maze[cur.x][cur.y]-'0') next.step++; //方向与以前不同,就消耗量加1 if(check(next.x, next.y) && next.step < TIME[next.x][next.y]) { TIME[next.x][next.y] = next.step; Q.push(next); } } } return ; } void read_case() { for(int i = 1; i <= n; i++) scanf("%s", maze[i]+1); } void solve() { read_case(); int q; scanf("%d", &q); while(q--) { init(); int bx, by, ex, ey; scanf("%d%d%d%d", &bx, &by, &ex, &ey); bfs(bx, by, ex, ey); printf("%d\n", TIME[ex][ey]); } return ; } int main() { while(~scanf("%d%d", &n, &m)) { solve(); } return 0; }