1016.cpp

我的URAL的1000 ~ 1050 的全部代码 包含WA 最后AC的程序 有2~3个比较难的是MAIGO的程序

//状态 8*8*24 华丽的dijkstra吧

#include <iostream>
#include <math.h>
using namespace std;

const int maxint = 0x0f0f0f0f;
int state[6];	//0->front 1->left 2->top 3->bottom 4->right 5->back 原程序这里错了？

int Left[6][6] = {
						-1,2,4,1,3,-1,
						3,-1,0,5,-1,2,
						1,5,-1,-1,0,4,
						4,0,-1,-1,5,1,
						2,-1,5,0,-1,3,
						-1,3,1,4,2,-1
						};//Left[i][j]: i: front j: bottom
int dis[9][9][6][6];
int dir[9][9][6][6];

int sx,sy,ex,ey;

void update( int x0, int y0, int f, int b, int come, int s)
{
	int i, j, k;
	if( s + state[b] < dis[x0][y0][f][b] )
	{
		dis[x0][y0][f][b] = s + state[b];
		dir[x0][y0][f][b] = come;
	}
}

void print( int x, int y, int f, int b )
{
	int i, j, k;
	switch (dir[x][y][f][b])
	{
		case -1: print(x,y-1,5-b,f); break;
		case -2: print(x-1,y,f,Left[f][b]); break;
		case -3: print(x,y+1,b,5-f); break;
		case -4: print(x+1,y,f,5-Left[f][b]); break;
		default: break;
	}
	printf("%c%d ", x + 'a' -1, y );
}
void dijkstra()
{
	int i,j,k,l,f,b,x,y,min;
	memset( dis , 15 ,sizeof(dis) );
	dis[sx][sy][0][3] = state[3];
	dir[sx][sy][0][3] = -5;
	x = sx; y = sy; f = 0; b = 3;
	min = state[3];
	
	do
	{
		if( y < 8 )update(x, y + 1, b, 5 - f,  1,min);
		if( x < 8 )update(x+1,y,f,5-Left[f][b],2,min);
		if( y > 1 )update(x, y - 1, 5 - b, f,  3,min);
		if( x > 1 )update(x-1,y,f,Left[f][b],  4,min); 
		min = maxint + 1;
		for( i = 1; i < 9; i++ )
			for( j = 1; j < 9; j++ )
				for( k = 0; k < 6; k++ )
					for( l = 0; l < 6; l++ )
						if ( dir[i][j][k][l] >= 0 && dis[i][j][k][l] < min )
						{min = dis[i][j][k][l]; x = i; y = j; f = k; b = l;}
		dir[x][y][f][b] = - dir[x][y][f][b];  
	}while( x != ex || y != ey );
	
	printf("%d ",dis[ex][ey][f][b]);
	print(ex,ey,f,b);
	printf("\n");
}
int main()
{

	freopen("1016.in","r",stdin);
	int i;
	char a;
	
	scanf( "%c%d",&a,&sy );
	sx = a - 'a' + 1;

	scanf( "%c", &a );
	scanf( "%c%d",&a,&ey );
	ex = a - 'a' + 1;
	
	scanf("%d%d%d%d%d%d", state, state + 5, state + 2, state + 4, state + 3, state + 1); // different?
	memset( dir, 0 , sizeof(dir) );
	dijkstra();
	return 0;
}