Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
当每步判断發現比已有值大的时猴,还要继续而不熊break!因为需要mod3//============================================================================ // Name : main1376.cpp // Author : // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================ #include <iostream> #include <stdio.h> #include <queue> #include <algorithm> using namespace std; struct e{ int x,y,dir,dist; }; bool operator<(const e& e1, const e& e2){ return e1.dist > e2.dist; } int m,n; bool block[60][60]; int dist[60][60][4]; const int MXINT = 2147483647; int startX, startY, endX, endY, dir; int dirVec[4][2] = {{-1,0},{0,1},{1,0},{0,-1}}; int toDir(char c){ if(c=='n') return 0; if(c=='e') return 1; if(c=='s') return 2; if(c=='w') return 3; return -1; } bool init(){ scanf("%d%d", &m,&n); if(!m) return 0; for(int i = 0; i <= m; i++){ for(int j = 0; j <= n; j++){ if(!i || !j || (i==m) || (j==n)) block[i][j] = 1; else block[i][j] = 0; } } for(int i = 0; i <= m; i++){ for(int j = 0; j <= n; j++){ for(int k = 0; k < 4; k++) dist[i][j][k] = MXINT; } } for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ int temp; scanf("%d", &temp); if(temp){ block[i][j] = 1; block[i][j+1] = 1; block[i+1][j] = 1; block[i+1][j+1] = 1; } } } char fx[9]; scanf("%d%d%d%d%s", &startX, &startY, &endX, &endY, fx); dir = toDir(fx[0]); return 1; } int main() { while(init()){ priority_queue<e> pqe; if(block[startX][startY] || block[endX][endY]){ printf("-1\n"); continue; } dist[startX][startY][dir] = 0; dist[startX][startY][(dir+1)%4] = 1; dist[startX][startY][(dir+2)%4] = 2; dist[startX][startY][(dir+3)%4] = 1; e temp; int cnt; temp.x = startX, temp.y = startY; cnt = 0; temp.dir = dir; while(!block[temp.x][temp.y]){ dist[temp.x][temp.y][temp.dir] = (cnt+2)/3; temp.dist = (cnt+2)/3; pqe.push(temp); temp.x += dirVec[temp.dir][0], temp.y += dirVec[temp.dir][1]; cnt++; } temp.x = startX, temp.y = startY; cnt = 0; temp.dir = (dir+1)%4; while(!block[temp.x][temp.y]){ dist[temp.x][temp.y][temp.dir] = 1+(cnt+2)/3; temp.dist = 1+(cnt+2)/3; pqe.push(temp); temp.x += dirVec[temp.dir][0], temp.y += dirVec[temp.dir][1]; cnt++; } temp.x = startX, temp.y = startY; cnt = 0; temp.dir = (dir+3)%4; while(!block[temp.x][temp.y]){ dist[temp.x][temp.y][temp.dir] = 1+(cnt+2)/3; temp.dist = 1+(cnt+2)/3; pqe.push(temp); temp.x += dirVec[temp.dir][0], temp.y += dirVec[temp.dir][1]; cnt++; } temp.x = startX, temp.y = startY; cnt = 0; temp.dir = (dir+2)%4; while(!block[temp.x][temp.y]){ dist[temp.x][temp.y][temp.dir] = 2+(cnt+2)/3; temp.dist = 2+(cnt+2)/3; pqe.push(temp); temp.x += dirVec[temp.dir][0], temp.y += dirVec[temp.dir][1]; cnt++; } while(!pqe.empty()){ temp = pqe.top(); pqe.pop(); if(temp.dist > dist[temp.x][temp.y][temp.dir]) continue; int dir1 = (temp.dir+1)%4, dir2 = (temp.dir+3)%4; int tmpx = temp.x+dirVec[dir1][0], tmpy = temp.y+dirVec[dir1][1]; cnt = 1; while(!block[tmpx][tmpy]){ if(temp.dist+1+(cnt+2)/3 < dist[tmpx][tmpy][dir1]){ e tp; tp.x = tmpx, tp.y = tmpy, tp.dir = dir1, tp.dist = temp.dist+1+(cnt+2)/3; dist[tmpx][tmpy][dir1] = tp.dist; pqe.push(tp); } //else continue; tmpx += dirVec[dir1][0]; tmpy += dirVec[dir1][1]; cnt++; } cnt = 1; tmpx = temp.x+dirVec[dir2][0], tmpy = temp.y+dirVec[dir2][1]; while(!block[tmpx][tmpy]){ if(temp.dist+1+(cnt+2)/3 < dist[tmpx][tmpy][dir2]){ e tp; tp.x = tmpx, tp.y = tmpy, tp.dir = dir2, tp.dist = temp.dist+1+(cnt+2)/3; dist[tmpx][tmpy][dir2] = tp.dist; pqe.push(tp); } //else continue; tmpx += dirVec[dir2][0]; tmpy += dirVec[dir2][1]; cnt++; } } int mn = MXINT; for(int i = 0; i < 4; i++){ if(dist[endX][endY][i] < mn) mn = dist[endX][endY][i]; } if(mn==MXINT) printf("-1\n"); else printf("%d\n", mn); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator