献给阿尔吉侬的花束

心已赠人 2024-03-30 17:08 112阅读 0赞

## 献给阿尔吉侬的花束 ##

阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。

今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。

现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。

迷宫用一个 R×C 的字符矩阵来表示。

字符 S 表示阿尔吉侬所在的位置，字符 E 表示奶酪所在的位置，字符 \# 表示墙壁，字符 . 表示可以通行。

阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。

输入格式  
第一行是一个正整数 T，表示一共有 T 组数据。

每一组数据的第一行包含了两个用空格分开的正整数 R 和 C，表示地图是一个 R×C 的矩阵。

接下来的 R 行描述了地图的具体内容，每一行包含了 C 个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。

输出格式  
对于每一组数据，输出阿尔吉侬吃到奶酪的最少单位时间。

若阿尔吉侬无法吃到奶酪，则输出“oop!”（只输出引号里面的内容，不输出引号）。

每组数据的输出结果占一行。

数据范围  
1<T≤10,  
2≤R,C≤200  
输入样例：  
3  
3 4  
.S…  
\#\#\#.  
…E.  
3 4  
.S…  
.E…  
…  
3 4  
.S…

#####  #####

…E.  
输出样例：  
5  
1  
oop!

### 算法思路 ###

用 g\[N\]\[N\] 接收地图。  
d\[N\]\[N\] 存储到每个点的路径长度。

从起点出发，广度优先遍历地图：

起点入队。  
如果队列非空，一直执行下面语句：

队头出队。  
遍历队头的上下左右四个方向：如果是 ‘.’ 走过去，并且该位置入队，该点对应的d值更新为队头的d + 1，该点更新为’\#’,表示走过了。如果是 ‘\#’ 不做处理，如果是 ‘E’,走到了终点，输出该点对应的 d 值。  
如果队列为空，还没有找到终点，则无法到达，输出 oop!。

### 提交代码 ###

C++

#include<iostream>
    #include<queue>
    #include<cstring>
    using namespace std;
    
    const int N = 210;
    typedef pair<int, int> PII;
    int t, a, c;
    char g[N][N];
    int d[N][N];
    
    PII start, tend;
    
    int bfs()
    {
        
        queue<PII> q;
        int dx[4] = {
        -1, 0, 1, 0};
        int dy[4] = {
        0, 1, 0, -1};
        memset(d, -1, sizeof d);
        d[start.first][start.second] = 0;
        q.push(start);
        while(q.size())
        {
        
            auto cur = q.front();
            q.pop();
            
            for (int i = 0; i < 4; ++ i)
            {
        
                int x = cur.first + dx[i];
                int y = cur.second + dy[i];
                if (x > 0 && x <= a && y > 0 && y <= c && d[x][y] == -1 
                && (g[x][y] == '.' || g[x][y] == 'E')) 
                {
        
                    d[x][y] = d[cur.first][cur.second] + 1;
                    if (g[x][y] == 'E') return d[x][y];
                    q.push(make_pair(x, y));
                }
            }
        }
        return d[tend.first][tend.second];
    }
    int main()
    {
        
        scanf ("%d", &t);    
        while(t-- > 0)
        {
        
            scanf ("%d%d", &a, &c);
            for (int i = 1; i <= a; ++ i)
            {
        
                for (int j = 1; j <= c; ++ j)
                {
        
                    scanf (" %c", &g[i][j]); // 输入的时候不要忘记这个%c前面的空格
                    if (g[i][j] == 'S') start = make_pair(i, j);
                    else if (g[i][j] == 'E') tend = make_pair(i, j);
                }
            }
            int res = bfs();
            if (res == -1 || res == 0) puts("oop!");
            else printf ("%d\n", res);
        }
        return 0;
    }

Java

import java.util.*;
    
    
    import java.io.*;
    
    public class Main 
    {
        
    	static int N = 210;
    	static int [][] d = new int [N][N];
    	static char [][] g = new char [N][N];
    	static PII start;
    	static PII tend;
    	static int t, a, c;
    	
    	static int bfs()
    	{
        
    		Queue<PII> q = new LinkedList<PII>();
    		int [] dx = {
        -1, 0, 1, 0};
    		int [] dy = {
        0, 1, 0, -1};
    		for (int i = 0; i < a; ++ i) Arrays.fill(d[i], -1);
    		q.add(start);
    		d[start.first][start.second] = 0;
    		while(!q.isEmpty())
    		{
        
    			PII cur = q.poll();
    			for (int i = 0; i < 4; ++ i)
    			{
        
    				int x = cur.first + dx[i];
    				int y = cur.second + dy[i];
    				if (x >= 0 && x < a && y >= 0 && y < c)
    				{
        
    					if (d[x][y] != -1) continue;
    					if (g[x][y] == '#') continue;
    					d[x][y] = d[cur.first][cur.second] + 1;
    					if (x == tend.first && y == tend.second) return d[x][y];
     					q.add(new PII(x, y));
    				}
    			}
    		}
    		return -1;
    	}
    	public static void main(String[] args) throws IOException
    	{
        
    		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    		t = Integer.parseInt(reader.readLine());
    		while(t -- > 0)
    		{
        
    			String [] strs = reader.readLine().split(" ");
    			a = Integer.parseInt(strs[0]);
    			c = Integer.parseInt(strs[1]);
    			for (int i = 0; i < a; ++ i)
    			{
        				
    				g[i] = reader.readLine().toCharArray();
    				// System.out.println(g[i]);
    				for (int j = 0; j < c; ++ j)
    				{
        
    					if (g[i][j] == 'S') start = new PII(i, j);
    					else if (g[i][j] == 'E') tend = new PII(i, j);
    				}
    			}	
    			// System.out.println(start.first + " " + start.second);
    			int res = bfs();
    			if (res == -1)
    			{
        
    				writer.write("oop!\n");
    				writer.flush();
    				// System.out.println("oop!");
    			}
    			else 
    			{
        
    				writer.write(res+"\n");
    				writer.flush();
    				//System.out.println(res);
    			}
    		}
    	}
    }
    class PII
    {
        
    	int first, second;
    	public PII(int x, int y)
    	{
        
    		this.first = x;
    		this.second = y;
    	}
    }

Python

import queue
    T= int(input())
    def dfs(start,end):
        dist[start[0]][start[1]]=0
        dx,dy=[-1,0,1,0],[0,1,0,-1]
        que=[]
        que.append(start)
        while len(que):
            t= que.pop(0)
            for i in range(4):
                Y,X= t[0]+dx[i],t[1]+dy[i]
                #出界
                if(X<0 or X>=line or Y<0 or Y>=row):continue
                #障碍物
                if(g[Y][X]=='#'):continue
                #已经走过了
                if(dist[Y][X]!=-1):continue
                dist[Y][X]= dist[t[0]][t[1]]+1
                if(end==[Y,X]):
                    return dist[Y][X]
                que.append([Y,X])
        return -1
    for i in range((T)):
        s = list(map(int, input().split(' ')))
        row, line = s[0], s[1]
        dist=[[-1]*line for l in range(row)]
        start, end = [], []
        g=[]
        for k in range(row):
            g.append(input())
        for h in range(len(g)):
            for w in range(line):
                if(g[h][w]=='S'):
                    start=[h,w]
                if(g[h][w]=='E'):
                    end=[h,w]
        t1= dfs(start,end)
        if(t1==-1):
            print('oop!')
        else:
            print(t1)