zoj 3890 Wumpus

#include<cstdio>#include<cmath>#include<queue>#include<vector>#include<stack>#include<map>#include<string>#include<cstring>#include<algorithm>#include<iostream>using namespace std;typedef long long ll;const ll maxn = 25;int T, n, flag, x, y;int mp[maxn][maxn];int f[maxn][maxn][4][2];struct point{int x, y, d, v;point(int x, int y, int d, int v) :x(x), y(y), d(d), v(v){}};int bfs(){queue<point> p;p.push(point(0, 0, 0, 0));if (mp[0][0] == 1) return -1;f[0][0][0][0] = 0;int x, y, d, v;while (!p.empty()){point q = p.front();p.pop();if (f[q.x][q.y][q.d][q.v] > 98) continue;x = q.x;y = q.y;v = q.v;if (mp[x][y] == 3 && f[x][y][q.d][1] > f[x][y][q.d][0]){f[x][y][q.d][1] = f[x][y][q.d][0];p.push(point(x, y, q.d, 1));}d = (q.d + 1) % 4;if (f[x][y][d][v] > f[x][y][q.d][v] + 1){f[x][y][d][v] = f[x][y][q.d][v] + 1;p.push(point(x, y, d, v));}d = (q.d + 3) % 4;if (f[x][y][d][v] > f[x][y][q.d][v] + 1){f[x][y][d][v] = f[x][y][q.d][v] + 1;p.push(point(x, y, d, v));}d = q.d;if (d == 0) ++x;if (d == 1) --y;if (d == 2) --x;if (d == 3) ++y;if (x >= 0 && x < n&&y >= 0 && y<n)if (mp[x][y] != 1 && mp[x][y] != 2)if (f[x][y][d][v] > f[q.x][q.y][d][v] + 1){f[x][y][d][v] = f[q.x][q.y][d][v] + 1;p.push(point(x, y, d, v));}}int ans = f[0][0][0][1];for (int i = 1; i < 4; i++) ans = min(ans, f[0][0][i][1]);ans = 980 - ans * 10;if (ans < 0) return -1;return ans;}int main(){scanf("%d", &T);while (T--){scanf("%d", &n);memset(mp, 0, sizeof(mp));while (scanf("%d%d%d", &flag, &x, &y) == 3){if (x == -1 && y == -1 && flag == -1) break;mp[x][y] = flag;}memset(f, 1, sizeof(f));printf("%dn", bfs());}return 0;}