| ||||||||||
| 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