首页 > ACM题库 > 九度OJ > 九度-1365-贝多芬第九交响曲[解题代码]
2013
12-13

九度-1365-贝多芬第九交响曲[解题代码]

题目描述:

         也许不是所有人都知道贝多芬的“第九交响曲”,但是所有人都一定知道《欢乐颂》这首歌,它就是来自于贝多芬第九交响曲《合唱》的第四乐章,玄影游侠受朋友推荐听了这部交响曲,并且被这部交响曲深深地打动。

         2012年的11日上午,在奥地利首都维也纳新年音乐会上,音乐家们会演奏这首交响曲,他现在非常想去现场感受一下。但是他还是学生,并没有很多积蓄。音乐会的举办方考虑到一些学生的实际情况,他们专门安排了一个智力挑战赛,完成挑战赛的人将免费获得一张维也纳音乐会的门票。

         挑战赛规则如下:

         现在在一块空的场地上会有一个大的二维棋盘,裁判会给你指定初始位置及一座贝多芬雕像所处的位置,你开始时就站在裁判指定的初始位置处,你的目标是跳到贝多芬雕像的位置。为了给比赛增加一定的难度,你在棋盘上行走时,必须按照中国象棋中的马的走步方式来走。玩过中国象棋的人都知道,马走“日”,象走“田”。最后,你只需要告诉裁判最少多少步能到达贝多芬的雕像。如果根本就到不了贝多芬的雕像处,你直接告诉裁判就可以了。

         玄影游侠站在棋盘的某一个位置,不知道该如何走,他知道你们都学过程序设计,所以想请你们帮帮忙编一个程序来帮助他找到想要到达贝多芬的雕像处所需要的最少的步数。

输入:

         每组测试数据可能有多组输入,对于每一组输入,

         输入的第一行包括一个整数N(1<=N<=100),代表棋盘的大小是N*N

         输入的第二行包括四个数start_x, start_y, end_x, end_y(1 <= start_x,start_y,end_x,end_y <= N),分别代表你开始时的位置的x坐标和y坐标以及贝多芬雕像的x坐标和y坐标。

输出:

         如果你能够到达贝多芬雕像的位置,请输出最少需要多少步。

         如果不能到达,则输出-1

样例输入:
3
1 1 3 2
3
1 1 2 2
样例输出:
1
-1
提示:

         注意,棋盘并不是中国象棋的棋盘,你可以把它理解成N*N的类似于五子棋的棋盘。


cpp 代码如下:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;

const int MAXN = 107;
typedef struct Node{
	int x,y;
	int time;
}N,pN;

N s,e;
int visit[MAXN][MAXN];
int dir[8][2] = {
		{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2}
};

int bfs(int n){
	queue<N> Q;
	int i;
	N first,next;
	first.x = s.x;
	first.y = s.y;
	if(s.x == e.x && s.y == e.y)
		return 0;
	Q.push(first);
	while(!Q.empty()){
		first = Q.front();
		Q.pop();
		for(int i=0; i<8; i++){
			next.x = first.x + dir[i][0];
			next.y = first.y + dir[i][1];

			if(next.x>0 && next.x<=n && next.y>0 && next.y<=n && !visit[next.x][next.y]){
				next.time = first.time + 1;
				if(next.x == e.x && next.y==e.y)
					return next.time;
				visit[next.x][next.y] = 1;
				Q.push(next);
			}
		}
	}

	return -1;

}
int main(){
	int n;
	while(scanf("%d",&n) != EOF){
		scanf("%d %d %d %d",&s.x,&s.y,&e.x,&e.y);
		int i,j;
		memset(visit,0,sizeof(visit));
		printf("%d\n",bfs(n));
	}

	return 0;
}

/**************************************************************
	Problem: 1365
	User: coder
	Language: C++
	Result: Accepted
	Time:420 ms
	Memory:1568 kb
****************************************************************/

 


  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  2. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的