为什么会uke?
查看原帖
为什么会uke?
1048327
KANO07楼主2024/3/13 20:04

ExecutionResult(cpu_time=4, real_time=20, memory=569344, exit_code=0, signal=11, exceed=None)这是tle的意思吗?

#include<bits/stdc++.h>
#define endl '\n'	
using namespace std;
typedef long long ll;
int dir[4][2] = {1,0, 0,1, -1,0, 0,-1};
string g[2005];
int n,m;
int dis[2005][2005];
int vis[2005][2005];
pair<int,int> path[2005][2005];

void dij(int a, int b){
	dis[a][b] = 0;
	queue<pair<int,int>>q;
	q.push({1,1});
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if(vis[x][y]) continue;
		vis[x][y] = 1;
		for(int i = 0; i < 4; i++){
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
			if(nx < 1 || ny < 1 || nx > n || ny > m) continue;
			if(g[nx][ny] == g[x][y]) continue;
			if(dis[nx][ny] > dis[x][y] + 1){
				dis[nx][ny] = dis[x][y] + 1;
				path[nx][ny] = {x,y};
				q.push({nx, ny});
			} 
		}
	}
}
void print(int x, int y){
	stack<char>st;
	while(x != 0 && y != 0){
		int nx = path[x][y].first;
		int ny = path[x][y].second;
		if(nx > x) st.push('D');
		else if(nx < x) st.push('U');
		else{
			if(ny > y) st.push('R');
			else if(ny < y) st.push('L');
		}
		x = nx;
		y = ny;
	}
	while(!st.empty()){
		cout<<st.top();
		st.pop();
	} 
	cout<<endl;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i = 1; i <= n; i++){
			cin>>g[i];
			g[i] = " " + g[i]; 
			for(int j = 1; j <= m; j++){
				dis[i][j] = INT_MAX;
				vis[i][j] = 0;
				path[i][j].first = 0;
				path[i][j].second = 0;
			}
		}
		dij(1,1);
		if(dis[n][m] == INT_MAX){
			cout<<-1<<endl;
		} 
		else{
			cout<<dis[n][m]<<endl;
			path[1][1] = {0,0};
			print(n,m);
		}
	}
	return 0;
}
2024/3/13 20:04
加载中...