Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

当每步判断發現比已有值大的时猴,还要继续而不熊break!因为需要mod3

Posted by KatrineYang at 2016-09-30 04:35:40 on Problem 1376
//============================================================================
// 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator