Bloxorz II

C++14(g++5.4) 解法, 执行用时: 6ms, 内存消耗: 2396K, 提交时间: 2020-08-15 13:31:22

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int inf = 0x7fffffff;
int d[310][310][4],vis[310][310][4],ans = inf;
const int next_x[5][5] = {{-2,1,0,0},{-1,2,0,0},{-1,1,0,0}};
const int next_y[5][5] = {{0,0,-2,1},{0,0,-1,1},{0,0,-1,2}};
const int next_lie[5][5] = {{1,1,2,2},{0,0,1,1},{2,2,0,0}};
char ch[10];

struct node
{
    int x,y,lie;
};

void init()
{
    queue <node> q;
    node temp;
    temp.x = temp.y = 100;
    temp.lie = 0;
    vis[temp.x][temp.y][temp.lie] = 1;
    q.push(temp);
    while (!q.empty())
    {
        node u = q.front();
        q.pop();
        int x = u.x,y = u.y,lie = u.lie;
        for (int i = 0; i < 4; i++)
        {
            int nx = x + next_x[lie][i],ny = y + next_y[lie][i],nlie = next_lie[lie][i];
            if (nx < 0 || nx > 200 || ny < 0 || ny > 200)
                continue;
            if (vis[nx][ny][nlie])
                continue;
            d[nx][ny][nlie] = d[x][y][lie] + 1;
            vis[nx][ny][nlie] = 1;
            node temp;
            temp.x = nx;
            temp.y = ny;
            temp.lie = nlie;
            q.push(temp);
        }
    }
}

int calc(int x,int y)
{
    int res = 0,k = 0;
    if (x > 200)
    {
        k = (x - 200) / 3 + 1;
        res += k * 2;
        x -= k * 3;
    }
    if (y > 200)
    {
        k = (y - 200) / 3 + 1;
        res += k * 2;
        y -= k * 3;
    }
    res += d[x][y][0];
    return res;
}

int main()
{
    init();
    while (scanf("%s",ch) != EOF)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x += 100;
        y += 100;
        if (ch[0] == 'U')
            printf("%d\n",calc(x,y));
        ans = inf;
        if (ch[0] == 'H')
        {
            for (int i = -2; i <= 2; i++)
                ans = min(ans,calc(x + i,y - 1) + abs(i) + 1);
            for (int i = -2; i <= 2; i++)
                ans = min(ans,calc(x + i,y + 2) + abs(i) + 1);
            printf("%d\n",ans);
        }
        if (ch[0] == 'V')
        {
            for (int i = -2; i <= 2; i++)
                ans = min(ans,calc(x - 1,y + i) + abs(i) + 1);
            for (int i = -2; i <= 2; i++)
                ans = min(ans,calc(x + 2,y + i) + abs(i) + 1);
            printf("%d\n",ans);
        }
    }

    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 6ms, 内存消耗: 1120K, 提交时间: 2022-08-03 10:33:31

#include<bits/stdc++.h>
using namespace std;
const int N=210;
const int nxt_x[3][4]={{0,0,-2,1},{0,0,-1,1},{0,0,-1,2}};
const int nxt_y[3][4]={{-2,1,0,0},{-1,2,0,0},{-1,1,0,0}};
const int nxt_lie[3][4]={{1,1,2,2},{0,0,1,1},{2,2,0,0}};
int d[N][N][3];
bool v[N][N][3];char c[2];
struct node
{
	int x,y,lie;
	node(){}
	node(int x,int y,int lie):x(x),y(y),lie(lie){}
};
bool pd(int x,int y){return x>0&&x<=200&&y>0&&y<=200;}
void pre()
{
	node now,nxt;queue<node>q;
	memset(d,-1,sizeof(d));memset(v,false,sizeof(v));
	now=node(100,100,0);d[100][100][0]=0;
	q.push(now);v[100][100][0]=true;
	while(!q.empty())
	{
		now=q.front();q.pop();
		for(int i=0;i<4;i++)
		{
			nxt=now;
			nxt.x+=nxt_x[now.lie][i];nxt.y+=nxt_y[now.lie][i];
			nxt.lie=nxt_lie[now.lie][i];
			if(v[nxt.x][nxt.y][nxt.lie]||!pd(nxt.x,nxt.y))continue;
			d[nxt.x][nxt.y][nxt.lie]=d[now.x][now.y][now.lie]+1;
			v[nxt.x][nxt.y][nxt.lie]=1;q.push(nxt);
		}
	}
}
int calc(int x,int y)
{
	int ans=0;
	if(!pd(x,y))
	{
		if(x>200)
		{
			int k=(x-200)/3+2;
			ans+=k*2;
			x-=k*3;
		}
		if(y>200)
		{
			int k=(y-200)/3+2;
			ans+=k*2;
			y-=k*3;
		}
	}
	return ans+d[x][y][0];
}
int main()
{
	pre();
	while(scanf("%s",c)!=EOF)
	{
		int x,y;scanf("%d%d",&x,&y);
		int ans=2e9;x+=100,y+=100;
		if(c[0]=='U')ans=min(ans,calc(x,y));
		if(c[0]=='H')
		{
			for(int i=-2;i<=2;i++)
			{
				ans=min(ans,calc(x-i,y-1)+1+abs(i));
				ans=min(ans,calc(x-i,y+2)+1+abs(i));
			}
		}
		else if(c[0]=='V')
		{
			for(int i=-2;i<=2;i++)
			{
				ans=min(ans,calc(x-1,y+i)+1+abs(i));
				ans=min(ans,calc(x+2,y+i)+1+abs(i));
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

C++ 解法, 执行用时: 6ms, 内存消耗: 1036K, 提交时间: 2021-12-11 14:51:46

#include<bits/stdc++.h>
using namespace std;
int nx[3][4]={0,0,-2,1,0,0,-1,1,0,0,-1,2},ny[3][4]={-2,1,0,0,-1,2,0,0,-1,1,0,0},nl[3][4]={1,1,2,2,0,0,1,1,2,2,0,0},d[201][201][3],x,y;
bool v[201][201][3];
char c[2];
struct node{
	int x,y,l;
	node(){}
	node(int x,int y,int l):x(x),y(y),l(l){}
};
bool pd(int x,int y){return x>0&&x<=200&&y>0&&y<=200;}
void pre(){
	node now,nxt;
	queue<node>q;
	memset(d,-1,sizeof(d));
	memset(v,0,sizeof(v));
	now=node(100,100,0);
	d[100][100][0]=0;
	q.push(now);
	v[100][100][0]=1;
	while(!q.empty()){
		now=q.front();q.pop();
		for(int i=0;i<4;i++){
			nxt=now;
			nxt.x+=nx[now.l][i];nxt.y+=ny[now.l][i];
			nxt.l=nl[now.l][i];
			if(v[nxt.x][nxt.y][nxt.l]||!pd(nxt.x,nxt.y))continue;
			d[nxt.x][nxt.y][nxt.l]=d[now.x][now.y][now.l]+1;
			v[nxt.x][nxt.y][nxt.l]=1;q.push(nxt);
		}
	}
}
int calc(int x,int y){
	int ans=0;
	if(!pd(x,y)){
		if(x>200){int k=(x-200)/3+2;ans+=k*2;x-=k*3;}
		if(y>200){int k=(y-200)/3+2;ans+=k*2;y-=k*3;}
	}
	return ans+d[x][y][0];
}
int main(){
	pre();
	while(cin>>c){
		cin>>x>>y;
		int ans=2e9;
		x+=100;
		y+=100;
		if(c[0]=='U')ans=min(ans,calc(x,y));
		if(c[0]=='H')for(int i=-2;i<=2;i++)ans=min(ans,calc(x-i,y-1)+1+abs(i)),ans=min(ans,calc(x-i,y+2)+1+abs(i));
		else if(c[0]=='V')for(int i=-2;i<=2;i++)ans=min(ans,calc(x-1,y+i)+1+abs(i)),ans=min(ans,calc(x+2,y+i)+1+abs(i));
		cout<<ans<<"\n";
	}
	return 0;
}

详情