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

H2O题一个!先bfs祘出棋盘上任意两点的馬距离,然后暴力即可

Posted by KatrineYang at 2016-08-24 21:52:14 on Problem 1178 and last updated at 2016-08-24 21:53:29
#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>

using namespace std;

int dist[64][64];

bool inRange(int x, int y){
	return x >= 0 && x < 8 && y >= 0 && y < 8;
}

inline int Abs(int x){
	if(x >= 0) return x;
	return -x;
}

void preprocess(){
	for(int i = 0; i < 64; i++){
		bool used[64] = {0};
		used[i] = 1;
		queue<int> bfs;
		bfs.push(i);
		dist[i][i] = 0;
		while(!bfs.empty()){
			int top = bfs.front();
			bfs.pop();
			int x = top/8, y = top%8;
			if(inRange(x-1, y-2) && !used[top-10]){
				used[top-10] = 1;
				dist[i][top-10] = dist[i][top]+1;
				bfs.push(top-10);
			}
			if(inRange(x-1, y+2) && !used[top-6]){
				used[top-6] = 1;
				dist[i][top-6] = dist[i][top]+1;
				bfs.push(top-6);
			}
			if(inRange(x+1, y-2) && !used[top+6]){
				used[top+6] = 1;
				dist[i][top+6] = dist[i][top]+1;
				bfs.push(top+6);
			}
			if(inRange(x+1, y+2) && !used[top+10]){
				used[top+10] = 1;
				dist[i][top+10] = dist[i][top]+1;
				bfs.push(top+10);
			}
			if(inRange(x-2, y-1) && !used[top-17]){
				used[top-17] = 1;
				dist[i][top-17] = dist[i][top]+1;
				bfs.push(top-17);
			}
			if(inRange(x-2, y+1) && !used[top-15]){
				used[top-15] = 1;
				dist[i][top-15] = dist[i][top]+1;
				bfs.push(top-15);
			}
			if(inRange(x+2, y-1) && !used[top+15]){
				used[top+15] = 1;
				dist[i][top+15] = dist[i][top]+1;
				bfs.push(top+15);
			}
			if(inRange(x+2, y+1) && !used[top+17]){
				used[top+17] = 1;
				dist[i][top+17] = dist[i][top]+1;
				bfs.push(top+17);
			}
		}
	}
}

int main() {
	preprocess();
	char str[250];
	scanf("%s", str);
	int len = strlen(str);
	int gs = len/2-1;
	int posKgx, posKgy;
	int posKnx[64], posKny[64];
	posKgx = (str[0]-'A'), posKgy = (str[1]-'1');
	for(int i = 0; i < gs; i++){
		posKnx[i] = (str[2*i+2]-'A'), posKny[i] = (str[2*i+3]-'1');
	}
	int mn = 2147483647;
	for(int rdz = 0; rdz < 64; rdz++){
		int rdzx = rdz/8, rdzy = rdz%8;
		int mnK = Abs(rdzx-posKgx) + Abs(rdzy-posKgy);
		for(int i = 0; i < gs; i++){
			mnK += dist[rdz][posKnx[i]*8+posKny[i]];
		}
		for(int getOn = 0; getOn < 64; getOn++){
			if(getOn == rdz) continue;
			int getOnx = getOn/8, getOny = getOn%8;
			int temp = Abs(getOnx-posKgx) + Abs(getOny-posKgy);
			int dz = 2147483647;
			for(int i = 0; i < gs; i++){
				int iP = posKnx[i]*8+posKny[i];
				int duozou = dist[iP][getOn] + dist[getOn][rdz] - dist[iP][rdz];
				if(duozou < dz){
					dz = duozou;
				}
			}
			temp += dz;
			for(int i = 0; i < gs; i++){
				temp += dist[posKnx[i]*8+posKny[i]][rdz];
			}
			if(temp < mnK) mnK = temp;
		}
		if(mnK < mn) mn = mnK;
	}
	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