求助6pts
查看原帖
求助6pts
555381
zlttcl楼主2022/10/5 14:05

RT,代码如下:

//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 310;
ll n,m,nx,ny,x,y,ex,ey;
ll ans = 0x3f3f3f3f;
int dx[5] = {0,-1,0,1,0};
int dy[5] = {0,0,-1,0,1};
char a[N][N];
bool p[N][N];
inline ll read(){
	ll x = 0, m = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') m = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		x = x * 10 + ch - 48;
		ch = getchar();
	}
	return x * m;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		write(-x);
		return;
	}
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}
inline bool pd(int x,int y){
	return x < 1 ||x > n || y < 1 || y > m;
}
inline void solve(int x,int y){
	bool Fi = false;
	for(int i = 1; i <= n; ++ i){
		for(int j = 1; j <= m; ++ j){
			if(i != x && j != y && a[i][j] == a[x][y]){
				nx = i, ny = j;
				Fi= true;
				break;
			}
		}
		if(Fi){
			break;
		}
	}
}
inline void dfs(int x,int y,int ex,int ey,ll now){
	if(x == ex && y == ey){
		ans = min(ans,now);
		return;
	}
	for(int i = 1; i <= 4; ++ i){
		int xx = x + dx[i], yy = y + dy[i];
		if(pd(xx,yy) || p[xx][yy] || p[xx][yy] == '#') continue;
		p[xx][yy] = true;
		if('A' <= a[xx][yy] && a[xx][yy] <= 'Z'){
			solve(xx,yy);
			if(!p[nx][ny]){
				p[nx][ny] = true;
				dfs(nx,ny,ex,ey,now + 1);
				p[nx][ny] = false;
			}
		}else{
			dfs(xx,yy,ex,ey,now + 1);
		}
		p[xx][yy] = false;
	}
}
signed main(){
	n = read(), m = read();
	for(int i = 1; i <= n; ++ i){
		for(int j = 1; j <= m; ++ j){
			cin >> a[i][j];
			if(a[i][j] == '@'){
				x = i, y = j;
			}else if(a[i][j] == '='){
				ex = i, ey = j;
			}
		}
	}
	p[x][y] = true;
	dfs(x,y,ex,ey,0);
	write(ans);
	return 0;
}

基本上都超时了

2022/10/5 14:05
加载中...