孙悟空救师傅

Java 解法, 执行用时: 190ms, 内存消耗: 18368K, 提交时间: 2023-07-09 09:14:37

import java.util.*;

class Node{
    int x , y ;

    @Override
    public boolean equals(Object o) {
        Node node = (Node) o;
        return x == node.x && y == node.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Point{
    int x , y  , step , time;
    Set<Node> set = new HashSet<>();

    public Point(int x, int y, int step, int time) {
        this.x = x;
        this.y = y;
        this.step = step;
        this.time = time;
    }
}

public class Main {

    public static Scanner sc = new Scanner(System.in);

    public static int[] movx = { 1 , 0 , -1 , 0};
    public static int[] movy = { 0 , -1 , 0 , 1};

    public static void main(String[] args) {
        int n = sc.nextInt() , m = sc.nextInt();
        char[][] map = new char[n][n];
        boolean[][][] vis = new boolean[10][n][n];
        int sx = 0, sy = 0;
        for (int i = 0; i < n; i++) {
            map[i] = sc.next().toCharArray();
            for (int j = 0; j < n; j++) {
                if(map[i][j] == 'K'){
                    sx = i;sy = j;
                }
            }
        }
        Deque<Point> deque = new LinkedList<>();
        deque.offer(new Point(sx , sy , 0 ,0));
        int ans = 0;
        while (!deque.isEmpty()){
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                Point poll = deque.poll();
                if(poll.time != ans){
                    deque.offer(poll);
                    continue;
                }
                int x = poll.x , y = poll.y ;
                if(vis[poll.step][x][y]) continue;
                vis[poll.step][x][y] = true;
                if(poll.step == m && map[x][y] == 'T'){
                    System.out.println(ans);
                    return;
                }
                for (int j = 0; j < 4; j++) {
                    int nx = x + movx[j];
                    int ny = y + movy[j];
                    if(nx >= 0 && nx < n && ny >= 0 && ny < n && map[nx][ny] != '#' && !vis[poll.step][nx][ny]){
                        if(map[nx][ny] == 'S' && !poll.set.contains(new Node(nx , ny))) {
                            Point point = new Point(nx, ny, poll.step, poll.time + 2);
                            point.set.add(new Node(nx , ny));
                            deque.offer(point);
                        }else if(Character.isDigit(map[nx][ny]) && map[nx][ny] == (char)(poll.step + 1 + '0')){
                            Point point = new Point(nx, ny, poll.step + 1, poll.time + 1);
                            point.set.addAll(poll.set);
                            deque.offer(point);
                        }else{
                            Point point = new Point(nx, ny, poll.step, poll.time + 1);
                            point.set.addAll(poll.set);
                            deque.offer(point);
                        }
                    }
                }
            }
            ans += 1;
        }
        System.out.println("impossible");
    }



}

C++(g++ 7.5.0) 解法, 执行用时: 33ms, 内存消耗: 640K, 提交时间: 2023-02-11 12:02:15

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

char mp[105][105];
int vis[105][105];
int n,m;
int sx,sy;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
map<pair<int,int>,int> pp;
struct node
{
    ll x,y,step,key;
    map<pair<int,int>,int> p;
};
queue<node> q;
ll bfs()
{
    memset(vis,-1,sizeof vis);
    q.push({sx,sy,0,0,pp});
    vis[sx][sy]=0;
    while(q.size())
    {
        auto u=q.front();
        q.pop();
        map<pair<int,int>,int>p(u.p);
        for(int i=0;i<4;i++)
        {
            int x=u.x+dx[i],y=u.y+dy[i];
            if(x<1||y<1||x>n||y>n) continue;
            if(vis[x][y]>=u.key) continue;
            vis[x][y]=u.key;
            if(mp[x][y]=='#') continue;
            else if(mp[x][y]=='T'&&u.key==m) return u.step+1;
            else if(mp[x][y]==u.key+'1')
            {
                q.push({x,y,u.step+1,u.key+1,p});
                vis[x][y]=u.key+1;
            }
            else if(mp[x][y]=='S')
            {
                if(p[{x,y}]==0) q.push({x,y,u.step+1,u.key,p});
                else
                {
                    p[{x,y}]=0;
                    q.push({x,y,u.step+2,u.key,p});
                    p[{x,y}]=1;
                }
            }
            else q.push({x,y,u.step+1,u.key,u.p});
        }
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
    {
        cin>>mp[i][j];
        if(mp[i][j]=='K') sx=i,sy=j;
        if(mp[i][j]=='S') pp[{i,j}]=1;
    }
    ll ans=bfs();
    if(ans!=-1) cout<<ans;
    else cout<<"impossible";
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 6ms, 内存消耗: 792K, 提交时间: 2023-05-11 20:30:10

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 105;
char g[N][N];
int dist[N][N][10];
int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

struct Ver {
	int x, y, sg;
};

int bfs(int sx, int sy) {
	memset(dist, 0x3f, sizeof dist);

	queue<Ver> q;
	q.push({sx, sy, 0});
	dist[sx][sy][0] = 0;
	
	while (q.size()) {
		auto t = q.front();
		q.pop();
		
		int x = t.x, y = t.y, sg = t.sg;
		
		if (g[x][y] == 'T' && sg == m) return dist[x][y][sg];
		
		for (int i = 0; i < 4; i ++ ) {
			int a = x + dx[i], b = y + dy[i];
			if (a >= 0 && a < n && b >= 0 && b < n && g[a][b] != '#') {
				int u = sg;
				if (g[a][b] >= '1' && g[a][b] <= '9') {
					if (u == (g[a][b] - '0' - 1)) {
						u ++ ;
					}
				}
				if (g[a][b] != 'S' && dist[a][b][u] > dist[x][y][sg] + 1) {
					dist[a][b][u] = dist[x][y][sg] + 1;
					q.push({a, b, u});
			 	}
			 	if (g[a][b] == 'S' && dist[a][b][u] > dist[x][y][sg] + 2) {
			 		g[a][b] = '.';
			 		dist[a][b][u] = dist[x][y][sg] + 2;
			 		q.push({a, b, u});
			 	}
			}
		}
	}
	
	return -1;
}

int main() {
	scanf("%d%d", &n, &m);
	
	int sx = 0, sy = 0;
	for (int i = 0; i < n; i ++ ) cin >> g[i];
	
	for (int i = 0; i < n; i ++ ) {
		for (int j = 0; j < n; j ++ ) {
			if (g[i][j] == 'K') {
				sx = i, sy = j;
				break;
			}
		}
	}
	
	int res = bfs(sx, sy);
	
	if (res == -1) printf("impossible");
	else printf("%d", res);
	
	return 0;
}

详情