列表

详情

NC51023. Bloxorz I

描述

Little Tom loves playing games. One day he downloads a little computer game called 'Bloxorz' which makes him excited. It's a game about rolling a box to a specific position on a special plane. Precisely, the plane, which is composed of several unit cells, is a rectangle shaped area. And the box, consisting of two perfectly aligned unit cube, may either lies down and occupies two neighbouring cells or stands up and occupies one single cell. One may move the box by picking one of the four edges of the box on the ground and rolling the box 90 degrees around that edge, which is counted as one move. There are three kinds of cells, rigid cells, easily broken cells and empty cells. A rigid cell can support full weight of the box, so it can be either one of the two cells that the box lies on or the cell that the box fully stands on. A easily broken cells can only support half the weight of the box, so it cannot be the only cell that the box stands on. An empty cell cannot support anything, so there cannot be any part of the box on that cell. The target of the game is to roll the box standing onto the only target cell on the plane with minimum moves.


The box stands on a single cell
The box lies on two neighbouring cells, horizontally
The box lies on two neighbouring cells, vertically

After Little Tom passes several stages of the game, he finds it much harder than he expected. So he turns to your help.

输入描述

Input contains multiple test cases. Each test case is one single stage of the game. It starts with two integers R and C(3 ≤ R, C ≤ 500) which stands for number of rows and columns of the plane. That follows the plane, which contains Rlines and C characters for each line, with 'O' (Oh) for target cell, 'X' for initial position of the box, '.' for a rigid cell, '#' for a empty cell and 'E' for a easily broken cell. A test cases starts with two zeros ends the input.
It guarantees that
There's only one 'O' in a plane.
There's either one 'X' or neighbouring two 'X's in a plane.
The first(and last) row(and column) must be '#'(empty cell).
Cells covered by 'O' and 'X' are all rigid cells.

输出描述

For each test cases output one line with the minimum number of moves or "Impossible" (without quote) when there's no way to achieve the target cell.

示例1

输入: 

7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######
0 0

输出: 

10

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 174ms, 内存消耗: 4564K, 提交时间: 2019-08-14 20:11:52 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
struct rec { int x, y, lie; };
char s[510][510];
rec st,ed;
int n,m,d[510][510][3];
queue<rec> q;
const int dx[4]={ 0,0,-1,1}, dy[4]={ -1,1,0,0};
bool valid(int x,int y){
	return x>=1&&y>=1&&x<=n&&y<=m;
}

void parse_st_ed(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(s[i][j] == 'O'){
				ed.x=i;
				ed.y=j;
				ed.lie=0;
				s[i][j]='.';
			}else if(s[i][j] == 'X'){
				for(int k=0;k<4;k++){
					int x=i+dx[k], y=j+dy[k];
					if(valid(x,y)&&s[x][y]=='X'){
						st.x=min(i,x);
						st.y=min(j,y);
						st.lie=k<2?1:2;
						s[i][j]=s[x][y]='.';
						break;
					}
				}
				if(s[i][j]=='X'){
					s[i][j]='.';
					st.x=i;
					st.y=j;
					st.lie=0;
				}
			}
		}
	}
}

bool valid(rec next){
	if(!valid(next.x,next.y))return 0;
	if(s[next.x][next.y]=='#')return 0;
	if(next.lie==0&&s[next.x][next.y]!='.')return 0;
	if(next.lie==1&&s[next.x][next.y+1]=='#')return 0;
	if(next.lie==2&&s[next.x+1][next.y]=='#')return 0;
	return 1;
}

const int next_x[3][4]={{0,0,-2,1},{0,0,-1,1},{0,0,-1,2}};
const int next_y[3][4]={{-2,1,0,0},{-1,2,0,0},{-1,1,0,0}};
const int next_lie[3][4]={{1,1,2,2},{0,0,1,1},{2,2,0,0}};

int bfs(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=0;k<3;k++){
				d[i][j][k]=-1;
			}
		}
	}
	
	while(q.size())q.pop();
	
	d[st.x][st.y][st.lie]=0;
	q.push(st);
	while(q.size()){
		rec now = q.front();
		q.pop();
		for(int i=0;i<4;i++){
			rec next;
			next.x=now.x+next_x[now.lie][i];
			next.y=now.y+next_y[now.lie][i];
			next.lie=next_lie[now.lie][i];
			if(!valid(next))continue;
			if(d[next.x][next.y][next.lie]==-1){
				d[next.x][next.y][next.lie]=d[now.x][now.y][now.lie]+1;
				q.push(next);
			}
			if(next.lie==ed.lie&&next.x==ed.x&&next.y==ed.y){
				return d[next.x][next.y][next.lie];
			}
		}	
	}
	return -1;
}
int main(){
	while(cin>>n>>m&&n){
		for(int i=1;i<=n;i++){
			scanf("%s",s[i]+1);
		}
		parse_st_ed();
		//cout<<st.x<<"\t"<<st.y<<"\t"<<st.lie<<endl;
		int ans=bfs();
		if(ans==-1){
			puts("Impossible");
		}else{
			cout<<ans<<endl;
		}
	}
	
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 171ms, 内存消耗: 3732K, 提交时间: 2022-11-03 21:16:31 

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

//0-3 左右上下，0-2 直立，横躺，竖躺
int n,m,way[510][510][3];
char mat[510][510];
const int next_x[3][4]={{0,0,-2,1},{0,0,-1,1},{0,0,-1,2}};
const int next_y[3][4]={{ -2,1,0,0 },{ -1,2,0,0 },{ -1,1,0,0 }};
const int next_lie[3][4]={{ 1,1,2,2 },{ 0,0,1,1 },{ 2,2,0,0 }};

struct dot
{
    int x,y,lie;
}sta,ed;

bool operator!=(dot a,dot b)
{
    return a.x!=b.x||a.y!=b.y||a.lie!=b.lie;
}

void check()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(mat[i][j]=='O') ed={i,j,0},mat[i][j]='.';
            else if(mat[i][j]=='X')
            {
                mat[i][j]='.';
                if(mat[i][j+1]=='X') sta={i,j,1},mat[i][j+1]='.';
                else if(mat[i+1][j]=='X') sta={i,j,2},mat[i+1][j]='.';
                else sta={i,j,0};
            }
        }
}

int judge(dot a)
{
    int i=a.x,j=a.y,t=a.lie;
    if(i<1||i>n||j<1||j>m) return 0;
    if(mat[i][j]=='#') return 0;
    if(t==0 && mat[i][j]=='E') return 0;
    if(t==1 && (j+1>m || mat[i][j+1]=='#')) return 0;
    if(t==2 && (i+1>n || mat[i+1][j]=='#')) return 0;
    return 1;
}

int bfs()
{
    queue<dot> q;
    memset(way,0,sizeof(way));
    while(q.size()) q.pop();
    q.push(sta);
    while(q.size())
    {
        dot now=q.front();
        q.pop();
        for(int k=0;k<4;k++)
        {
            dot temp={now.x+next_x[now.lie][k],
            now.y+next_y[now.lie][k],next_lie[now.lie][k]};
            if(!judge(temp)) continue;
            if(way[temp.x][temp.y][temp.lie]==0&&temp!=sta)
            {
                way[temp.x][temp.y][temp.lie]=way[now.x][now.y][now.lie]+1;
                q.push(temp);
                if(!(temp!=ed)) return way[temp.x][temp.y][temp.lie];
            }
        }
    }
    return -1;
}

int main(void)
{
    while(cin>>n>>m && n && m)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>mat[i][j];
        check();
        int ans=bfs();
        if(ans==-1) cout<<"Impossible"<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}

Java(javac 1.8) 解法, 执行用时: 581ms, 内存消耗: 45204K, 提交时间: 2020-10-11 22:51:03 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static char[][] g = new char[505][505];
	static boolean[][][] vis = new boolean[505][505][3];
	static int[][][] d = {{{-2,0,2},{1,0,2},{0,-2,1},{0,1,1}},{{-1,0,1},{1,0,1},{0,-1,0},{0,2,0}},{{-1,0,0},{2,0,0},{0,-1,2},{0,1,2}}};
	static int n,m;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			n = sc.nextInt();
			m = sc.nextInt();
			if(n==0) break;
			for(int i=0;i<n;i++) {
				g[i] = sc.next().toCharArray();
				
			}
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					Arrays.fill(vis[i][j], false);
				}
			}
			A s = null;
			A:for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					if(g[i][j] == 'X') {
						if(g[i][j+1]=='X')
							s = new A(i,j,1,0);
						else if(g[i+1][j]=='X')
							s = new A(i,j,2,0);
						else 
							s = new A(i,j,0,0);
						break A;
					}
				}
			}
			bfs(s);			
		}

	}
	public static void bfs(A s) {
		Queue<A> q = new LinkedList<A>();
		q.offer(s);
		vis[s.x][s.y][s.flag] = true;
		while(!q.isEmpty()) {
			A t = q.poll();
			//System.out.println(t.x+" "+t.y+" "+t.flag);
			if(g[t.x][t.y]=='O'&&t.flag==0) {
				System.out.println(t.step);
				return;
			}
			for(int i=0;i<4;i++) {
				A next = new A(t.x+d[t.flag][i][0],t.y+d[t.flag][i][1],d[t.flag][i][2],t.step+1);
				if(!ok(next.x,next.y)) continue;
				if(next.flag==0) {
					if(g[next.x][next.y]=='E') continue;
				}else if(next.flag==1) {
					if(!ok(next.x,next.y+1)) continue;
				}else if(next.flag==2) {
					if(!ok(next.x+1,next.y)) continue;
				}
				if(!vis[next.x][next.y][next.flag]) {
					vis[next.x][next.y][next.flag] = true;
					q.offer(next);
				}
			}
		}
		System.out.println("Impossible");
	}
	public static boolean ok(int x,int y) {
		if(x<0||x>=n||y<0||y>=m) return false;
		return g[x][y]!='#';
	}
}
class A{
	int x,y,flag,step;
	public A(int x,int y,int flag,int step) {
		this.x = x;
		this.y = y;
		this.flag = flag;
		this.step = step;
	}
}

C++ 解法, 执行用时: 137ms, 内存消耗: 16584K, 提交时间: 2021-12-02 21:41:27 

#include<bits/stdc++.h>
using namespace std;
int dx[3][4]={-2,1,0,0,-1,2,0,0,0,0,-1,1},dy[3][4]={0,0,-2,1,0,0,-1,1,-1,2,0,0},dz[3][4]={1,1,2,2,0,0,1,1,0,0,2,2},n,m,sx,sy,sz,ex,ey,b[1001][1001][4];
char g[1001][1001];
struct nn{int x,y,z,step;nn(){}nn(int _x,int _y,int _z,int _step){x=_x;y=_y;z=_z;step=_step;}};
queue<nn> q;
int ii(nn a){
    if(a.z==0&&!(a.x>n||a.x<1||a.y>m||a.y<1)&&!b[a.x][a.y][a.z]&&g[a.x][a.y]!='E'&&g[a.x][a.y]!='#')return 0;
    if(a.z==1&&!(a.x<1||a.x+1>n||a.y<1||a.y>m)&&!b[a.x][a.y][a.z]&&g[a.x][a.y]!='#'&&g[a.x+1][a.y]!='#')return 0;
    if(a.z==2&&!(a.x<1||a.x>n||a.y<1||a.y+1>m)&&!b[a.x][a.y][a.z]&&g[a.x][a.y]!='#'&&g[a.x][a.y+1]!='#')return 0;
    return 1;
}
int bfs(){
    memset(b,0,sizeof(b));
    while(q.size())q.pop();
    q.push(nn(sx,sy,sz,0));
    b[sx][sy][sz]=1;
    while(q.size()){
        nn now=q.front();
		q.pop();
        for(int i=0;i<4;i++){
            nn tmp;
            tmp=nn(now.x+dx[now.z][i],now.y+dy[now.z][i],dz[now.z][i],now.step+1);
            if(ii(tmp))continue;
            if(tmp.x==ex&&tmp.y==ey&&!tmp.z)return tmp.step;
            q.push(tmp);
            b[tmp.x][tmp.y][tmp.z]=1;
        }
    }
    return -1;
}
int main(){
    while(cin>>n>>m&&n){
        for(int i=1;i<=n;i++)scanf("%s",g[i]+1);
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
            if(g[i][j]=='O')ex=i,ey=j;
            else if (g[i][j]=='X'&&g[i+1][j]=='X')sx=i,sy=j,g[i+1][j]='.',sz=1;
            else if(g[i][j]=='X'&&g[i][j+1]=='X')g[i][j + 1]='.',sx=i,sy=j,sz=2;
            else if(g[i][j]=='X')sx=i,sy=j,sz=0;
        }
        int ans=bfs();
        if(ans==-1)cout<<"Impossible"<<"\n";
        else cout<<ans<<"\n";
    }
    return 0;
}

上一题

© 2024 nowcoder.com