Incomplete Chessboard

Incomplete ChessboardInchess,Kingisthemostimportantpiece.Itcanmoveleft,right,up,downordiagonally,butonly onesquareatatime,shownbelow.

In chess, King is the most important piece. It can move left, right, up, down or diagonally, but only 

one square at a time, shown below.

Incomplete Chessboard

Given two squares A(r1,c1), B(r2,c2), your task is to calculate the number of moves needed to move a 
king from A to B. To make the problem (slightly) harder, one square C(r3,c3) is removed from the 
chessboard, that means the king should never go into square C during his trip. In this problem, rows 
are numbered 1~8 from bottom to top, and columns are numbered 1~8 from left to right.
Input
There will be at most 10000 test cases. Each case contains 6 integers r1, c1, r2, c2, r3, c3 (1<=r1, c1, 
r2, c2, r3, c3<=8). Three squares A, B, C are always distinct.
Output
For each test case, print the case number and the minimum number of moves needed.

Sample Input
1 1 8 7 5 6
1 1 3 3 2 2

Output for Sample Input

Case 1: 7
Case 2: 3

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int r3,c3,r1,c1,r2,c2,cas=0,s[70][3],a[9][9],dx[8]={0,0,1,1,1,-1,-1,-1},dy[8]={1,-1,1,0,-1,1,0,-1};

#define MAX(a,b) ((a)>(b) ? (a):(b))
#define MIN(a,b) ((a)<(b) ? (a):(b))

void search(int x,int y)
{
	int head=0,tail=1,i;
	
	s[1][0]=x; s[1][1]=y; s[1][2]=0;
	
	while(head<tail)
	{
		head++;
		for(i=0;i<8;i++)
		{
			x=s[head][0]+dx[i]; y=s[head][1]+dy[i];
			if(!a[x][y]&&x>0&&x<=8&&y>0&&y<=8)
			{
				tail++;
				s[tail][0]=x;
				s[tail][1]=y;
				s[tail][2]=a[x][y]=s[head][2]+1;
				if(a[r2][c2]>0)
				{
					printf("Case %d: %d\n",++cas,a[r2][c2]);
					return;
				}
			}
		}
	}
}
int main()
{
	while(scanf("%d %d %d %d %d %d",&r1,&c1,&r2,&c2,&r3,&c3)!=EOF)
	{
		memset(a,0,sizeof(a));
		a[r1][c1]=1; a[r3][c3]=1;
		
		search(r1,c1);
	}
	return 0;
}
只听到从架构师办公室传来架构君的声音:
羌内恕己以量人兮,各兴心而嫉妒。有谁来对上联或下联?
本文来源编程高手在此,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/166095
0
 

发表评论