4 条题解

  • 1
    @ 2024-12-1 21:27:09

    纽币，三维搜索，爽了

    #include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 30 + 10;
const int INF = 0x3f3f3f3f;
struct node
{
	int x , y , z , time;
};
queue < node > q;
bool flag;
int dx [] = {1 , -1 , 0 , 0 , 0 , 0};
int dy [] = {0 , 0 , 1 , -1 , 0 , 0};
int dz [] = {0 , 0 , 0 , 0 , 1 , -1};
int l , n , m , sx , sy , sz , ex , ey , ez; 
char a [N] [N] [N];
bool check (int x , int y , int z)
{
	if (x >= 1 && x <= l && y >= 1 && y <= n && z >= 1 && z <= m && a [x][y][z] != '#')
	    return 1;
	return 0;
}
void bfs (int x , int y , int z)
{
	a [x] [y] [z] = '#';
	q.push((node) {x , y , z , 0});
	while ( !q.empty() )
	{
		node top = q.front();
		q.pop(); 
		if (top.x == ex && top.y == ey && top.z == ez)
		{
			printf ("%s%d%s\n" , "Escaped in " , top.time , " minute(s).");
			flag = 1;
			return;
		}
		for (int i = 0; i <= 5; i++)
		{
			int xx = top.x + dx [i]; 
			int yy = top.y + dy [i]; 
			int zz = top.z + dz [i];
			if (check (xx , yy , zz)) 
			{
				q.push((node) {xx , yy , zz , top.time + 1});
				a [xx] [yy] [zz] = '#';
			}
		}
	}
}
int main()
{
	    while (cin >> l >> n >> m)
	    {
	    	if (l == 0 && n == 0 && m == 0) return 0;
	    	for (int i = 1; i <= l; i++)
	    	{
	    		for (int j = 1; j <= n; j++)
	    		{
	    			for (int k = 1; k <= m; k++) 
	                {
	            	    cin >> a [i] [j] [k];
	            	    if (a [i] [j] [k] == 'S') sx = i , sy = j , sz = k;
	            	    if (a [i] [j] [k] == 'E') ex = i , ey = j , ez = k;
				    }
				}      
			} 
	        bfs (sx , sy , sz);     
			if (!flag)   
	            printf ("%s\n" , "Trapped!");
	        flag = 0;
		} 
		return 0;
}
    • 0
      @ 2026-4-9 21:16:17 
      #include <bits/stdc++.h>
using namespace std;
const int N = 30 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const long long LLINF = 0x3f3f3f3f3f3f3f3fLL;
char a[N][N][N];
struct Node{
	int x, y, z, tim;
};
int xx, yy, zz, sx, sy, sz, ex, ey, ez, dx[] = {1, -1, 0, 0, 0, 0}, dy[] = {0, 0, 1, -1, 0, 0}, dz[] = {0, 0, 0, 0, 1, -1};
bool flag;
queue <Node> q;
void bfs(int x, int y, int z){
	a[x][y][z] = '#';
	q.push((Node){x, y, z, 0});
	while(!q.empty()){
		Node t = q.front();
		q.pop();
		if(t.x == ex && t.y == ey && t.z == ez){
			cout << "Escaped in " << t.tim << " minute(s).\n";
			flag = true;
			return;
		}
		for(int i = 0 ; i < 6 ; i++){
			int nx = t.x + dx[i], ny = t.y + dy[i], nz = t.z + dz[i];
			if(nx >= 1 && nx <= xx && ny >= 1 && ny <= yy && nz >= 1 && nz <= zz && a[nx][ny][nz] != '#'){
				q.push((Node){nx, ny, nz, t.tim + 1});
				a[nx][ny][nz] = '#';
			}
		}
	}
}
int main(){
	while(cin >> xx >> yy >> zz){
		if(xx == 0 && yy == 0 && zz == 0) return 0;
		for(int i = 1 ; i <= xx ; i++){
			for(int j = 1 ; j <= yy ; j++){
				for(int k = 1 ; k <= zz ; k++){
					cin >> a[i][j][k];
					if(a[i][j][k] == 'S'){
						sx = i;
						sy = j;
						sz = k;
					}
					if(a[i][j][k] == 'E'){
						ex = i;
						ey = j;
						ez = k;
					}
				}
			}
		}
		bfs(sx, sy, sz);
		if(!flag) cout << "Trapped!\n";
		flag = false;
	}
	return 0;
}
      • 0
        @ 2024-12-3 12:42:48

        不判空居然没问题 判空AC：

        #include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 30 + 10;
const int INF = 0x3f3f3f3f;
struct node
{
	int x , y , z , time;
};
queue < node > q;
bool flag;
int dx [] = {1 , -1 , 0 , 0 , 0 , 0};
int dy [] = {0 , 0 , 1 , -1 , 0 , 0};
int dz [] = {0 , 0 , 0 , 0 , 1 , -1};
int l , n , m , sx , sy , sz , ex , ey , ez; 
char a [N] [N] [N];
bool check (int x , int y , int z)
{
	if (x >= 1 && x <= l && y >= 1 && y <= n && z >= 1 && z <= m && a [x][y][z] != '#')
	    return 1;
	return 0;
}
void bfs (int x , int y , int z)
{
	a [x] [y] [z] = '#';
	q.push((node) {x , y , z , 0});
	while ( !q.empty() )
	{
		node top = q.front();
		q.pop(); 
		if (top.x == ex && top.y == ey && top.z == ez)
		{
			printf ("%s%d%s\n" , "Escaped in " , top.time , " minute(s).");
			flag = 1;
			return;
		}
		for (int i = 0; i <= 5; i++)
		{
			int xx = top.x + dx [i]; 
			int yy = top.y + dy [i]; 
			int zz = top.z + dz [i];
			if (check (xx , yy , zz)) 
			{
				q.push((node) {xx , yy , zz , top.time + 1});
				a [xx] [yy] [zz] = '#';
			}
		}
	}
}
int main()
{
	    while (cin >> l >> n >> m)
	    {
	    	if (l == 0 && n == 0 && m == 0) return 0;
	    	for (int i = 1; i <= l; i++)
	    	{
	    		for (int j = 1; j <= n; j++)
	    		{
	    			for (int k = 1; k <= m; k++) 
	                {
	            	    cin >> a [i] [j] [k];
	            	    if (a [i] [j] [k] == 'S') sx = i , sy = j , sz = k;
	            	    if (a [i] [j] [k] == 'E') ex = i , ey = j , ez = k;
				    }
				}      
			} 
	        bfs (sx , sy , sz);     
			if (!flag)   
	            printf ("%s\n" , "Trapped!");
	        flag = 0;
	        while (!q.empty())  
	            q.pop();
		} 
		return 0;
}
        • 0
          @ 2022-7-9 15:54:39

          该比赛官方题解，如要AC，请将文件输入输出改为stdio。

          /* Contest   : Ulm Local Contest 1997 
 * Problem D : Dungeon Master
 * Method    : Breadth-First Search
 * Author    : Mark Dettinger
 * Date      : May 29, 1997
 */

#include <stdio.h>
#include <assert.h>

#define WHITE 0
#define GRAY 1
#define BLACK 2
#define oo 1000000000

typedef struct { int lev,row,col; } cell;

FILE *input;

int rows,cols,levels;
char dungeon[40][40][40];
int d[40][40][40],color[40][40][40];
cell queue[30000];
int head,tail;

void skip_line() { while (fgetc(input)!='\n'); }

void enqueue (int l, int i, int j)
{
  queue[tail].lev = l;
  queue[tail].row = i;
  queue[tail].col = j;
  tail++;
  color[l][i][j] = GRAY;
}

void dequeue (int *l, int *i, int *j)
{
  *l = queue[head].lev;
  *i = queue[head].row;
  *j = queue[head].col;
  head++;
  color[*l][*i][*j] = BLACK;
}

void visit (int level, int row, int col, int distance)
{
  if (level<0 || level>=levels || row<0 || row>=rows || col<0 || col>=cols || 
      dungeon[level][row][col]=='#' || color[level][row][col]!=WHITE) return;
  d[level][row][col] = distance;
  enqueue(level,row,col);
}

int read_case()
{
  int l,i;

  fscanf(input,"%d %d %d",&levels,&rows,&cols);
  if (levels==0 && rows==0 && cols==0) return 0;
  skip_line();
  for (l=0; l<levels; l++)
    for (i=0; i<=rows; i++)
      fgets(dungeon[l][i],40,input);
  return 1;
}

void solve_case()
{
  cell start;
  int l,i,j,newd;
  
  /* 1. Initialization */

  for (l=0; l<levels; l++)
    for (i=0; i<rows; i++)
      for (j=0; j<cols; j++)
	{
	  color[l][i][j] = WHITE;
	  d[l][i][j] = oo;
	  if (dungeon[l][i][j]=='S')
	    { start.lev = l; start.row = i; start.col = j; }
	}

  /* 2. Breadth-First Search */

  head = tail = 0;
  visit(start.lev,start.row,start.col,0);
  while (head!=tail)
    {
      dequeue(&l,&i,&j);
      if (dungeon[l][i][j]=='E') break;
      newd = d[l][i][j]+1;
      visit(l  , i-1, j  , newd);  /* North */
      visit(l  , i+1, j  , newd);  /* South */
      visit(l  , i  , j+1, newd);  /* East  */
      visit(l  , i  , j-1, newd);  /* West  */
      visit(l+1, i  , j  , newd);  /* Up    */
      visit(l-1, i  , j  , newd);  /* Down  */
    }

  /* 3. Output */

  if (dungeon[l][i][j]=='E')
    printf("Escaped in %d minute(s).\n",d[l][i][j]);
  else
    printf("Trapped!\n");
}

int main()
{
  input = fopen("dungeon.in","r");
  assert(input!=NULL);
  while (read_case()) solve_case();
  fclose(input);
  return 0;
}
          • 1

          地牢（Dungeon Master）

          信息

          ID
          1828
          时间
          1000ms
          内存
          256MiB
          难度
          6
          标签
          递交数
          130
          已通过
          37
          上传者
          1. Language
          2. 兼容模式
          3. 主题
          3. Worker 0, 17ms
          4. Powered by Hydro v5.0.0-beta.8 Community