|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
#include <iostream> #include <sstream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <list> #include <stack> using namespace std; #define MAXDEP 10000000 int dir[8][2] = {{1,1},{1,-1},{-1,1},{-1,-1},{1,0},{0,1},{-1,0},{0,-1}}; char board[1005][1005]; bool vis[1005][1005]; int m = 0,n = 0,cx = 0,cy = 0,rx = 0,ry = 0; struct factorType{ int shoe; int step; void fillmax(){ shoe = MAXDEP,step = MAXDEP; } } factor[1001][1001]; struct nodeType{ int x; int y; bool operator < (nodeType b) const{ if(factor[y][x].shoe == factor[b.y][b.x].shoe){ return factor[y][x].step > factor[b.y][b.x].step; } return factor[y][x].shoe > factor[b.y][b.x].shoe; } }; bool dijkstra(){ nodeType init; priority_queue<nodeType> q; init.y = cy,init.x = cx; factor[cy][cx].shoe = 0; factor[cy][cx].step = 0; q.push(init); while (!q.empty()) { nodeType now; now = q.top(); q.pop(); if (now.y == ry && now.x == rx) return true; if(vis[now.y][now.x])continue; vis[now.y][now.x] = true; for (int i = 0; i < 8; i++) { nodeType tmp; tmp.y = now.y + dir[i][0]; tmp.x = now.x + dir[i][1]; if (tmp.x < 1 || tmp.y < 1 || tmp.x > n || tmp.y > m || vis[tmp.y][tmp.x]|| board[tmp.y][tmp.x] == 0) { continue; } if (factor[tmp.y][tmp.x].shoe > factor[now.y][now.x].shoe + (board[now.y][now.x] != board[tmp.y][tmp.x])) { factor[tmp.y][tmp.x].shoe = factor[now.y][now.x].shoe + (board[now.y][now.x] != board[tmp.y][tmp.x]); factor[tmp.y][tmp.x].step = factor[now.y][now.x].step+1; q.push(tmp); }else if(factor[tmp.y][tmp.x].shoe == factor[now.y][now.x].shoe + (board[now.y][now.x] != board[tmp.y][tmp.x]) && (factor[tmp.y][tmp.x].step > factor[now.y][now.x].step+1)){ factor[tmp.y][tmp.x].step = factor[now.y][now.x].step+1; q.push(tmp); } } } return false; } int main(){ while (cin >> m >> n >> cy >> cx >> ry >> rx) { for (int i = 1; i <= m; i++) {//y dir getchar(); for (int j = 1; j <= n; j++) {//x dir factor[i][j].fillmax(); board[i][j] = getchar() - '0'; vis[i][j] = false; } } if (dijkstra()) { cout << factor[ry][rx].step+1 << ' ' << factor[ry][rx].shoe << endl; }else{ cout << 0 << ' ' << 0 << endl; } } return 0; } |
经过了极其艰辛（～3天）的过程终于把这个题肝出来了。
基本题型是最短路，采用dijkstra，利用优先队列做堆优化，之所以老不过是因为松弛写错了，当时错误地认为下一节点一定会换鞋，实际上应该判断一下是不是要换鞋，换鞋和不换鞋的松弛操作要分开进行。
