首页 > 代码库 > zoj3478
zoj3478
最短路
吐槽一下。。。最先开始写了个地图哈希,6kb,然后不是正解,又写了个spfa,4kb,还是不对,无奈抄标程,结果把spfa改成dijiestra就对了。。。
由于只有两个变量,所以我们设一个四维状态,d[x0][y0][x1][y1],然后就可以跑最短路了。如果是多维的话就得用哈希了。
但是那个终点的位置不固定,而且得做两次,因为控制的价钱不一样,所以两次取最小值。
#include<bits/stdc++.h> using namespace std; const int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0}; struct position { int x0, y0, x1, y1; position(int x0 = 0, int y0 = 0, int x1 = 0, int y1 = 0) : x0(x0), y0(y0), x1(x1), y1(y1) {} bool friend operator < (position A, position B) { return A.x0 < B.x0; } }; int T, sx0, sy0, sx1, sy1; queue<position> q; set<position> inq; int d[12][17][12][17]; char Map[12][17]; void spfa() { memset(d, 0x3f3f, sizeof(d)); q.push(position(sx0, sy0, sx1, sy1)); d[sx0][sy0][sx1][sy1] = 0; while(!q.empty()) { position x = q.front(); q.pop(); inq.erase(x); // if(x.x0 < 1 || x.x1 < 1 || x.y0 < 1 || x.y1 < 1 || x.x0 > 10 || x.x1 > 10 || x.y0 > 15 || x.y1 > 15 || (Map[x.x0][x.y0] == ‘O‘ && Map[x.x1][x.y1] == ‘O‘)) continue; if(Map[x.x0][x.y0] == ‘O‘ && Map[x.x1][x.y1] == ‘O‘) continue; for(int i = 0; i < 4; ++i) { position t = x; int cost = d[t.x0][t.y0][t.x1][t.y1]; if(Map[t.x0][t.y0] != ‘O‘) { t.x0 += dx[i]; t.y0 += dy[i]; cost += 2; if(Map[t.x0][t.y0] == ‘X‘) { t.x0 = x.x0; t.y0 = x.y0; } } if(Map[t.x1][t.y1] != ‘O‘) { t.x1 += dx[i]; t.y1 -= dy[i]; cost += 3; if(Map[t.x1][t.y1] == ‘X‘) { t.x1 = x.x1; t.y1 = x.y1; } } if(d[t.x0][t.y0][t.x1][t.y1] > cost) { d[t.x0][t.y0][t.x1][t.y1] = cost; if(inq.find(position(t.x0, t.y0, t.x1, t.y1)) == inq.end()) { inq.insert(position(t.x0, t.y0, t.x1, t.y1)); q.push(position(t.x0, t.y0, t.x1, t.y1)); } } } position t = x; int cost = d[t.x0][t.y0][t.x1][t.y1]; if(abs(x.x0 - x.x1) + abs(x.y0 - x.y1) == 1 && ((Map[x.x0][x.y0] == ‘O‘) ^ (Map[x.x1][x.y1] == ‘O‘))) { if(Map[x.x0][x.y0] == ‘O‘) { t.x0 = x.x1; t.y0 = x.y1; } else { t.x1 = x.x0; t.y1 = x.y0; } cost += 11; } if(d[t.x0][t.y0][t.x1][t.y1] > cost) { d[t.x0][t.y0][t.x1][t.y1] = cost; if(inq.find(position(t.x0, t.y0, t.x1, t.y1)) == inq.end()) { inq.insert(position(t.x0, t.y0, t.x1, t.y1)); q.push(position(t.x0, t.y0, t.x1, t.y1)); } } } printf("%d\n", d[1][8][1][8] == 1061109567 ? -1 : d[1][8][1][8]); } int main() { scanf("%d", &T); while(T--) { inq.clear(); for(int i = 0; i <= 12; ++i) for(int j = 0; j <= 17; ++j) Map[i][j] = ‘X‘; for(int i = 1; i <= 10; ++i) { char s[17]; scanf("%s", s + 1); for(int j = 1; j <= 15; ++j) { if(s[j] == ‘H‘) s[j] = ‘.‘; Map[i][j] = s[j]; } } scanf("%d%d%d%d", &sx0, &sy0, &sx1, &sy1); spfa(); } return 0; }
zoj3478
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。