#include<bits/stdc++.h>
using namespace std;
map<string,string> conveyor;
int tx[4] = {0,0,1,-1};
int ty[4] = {1,-1,0,0};
int jiyi[500][500];
int ans = INT_MAX;
int vis[500][500];
char mp[500][500];
string tong[1000];
int sx,sy;
int n,m;
int dfs(int x,int y,int t)
{
if(mp[x][y] == '=')
{
ans = min(ans,t);
return 1;
}
if(jiyi[x][y] <= t)
{
return 0;
}
jiyi[x][y] = t;
for(int i = 0;i<4;i++)
{
int nx = x + tx[i];int ny = y + ty[i];
if(nx >= 0 && nx < n && ny >= 0 && ny < m && mp[nx][ny] != '#' && vis[nx][ny] == 0)
{
if(mp[nx][ny] >= 'A' && mp[nx][ny] <= 'Z' && conveyor[to_string(nx) + " " + to_string(ny)] != "")
{
vis[nx][ny] = 1;
int mid = 0;
string s = conveyor[to_string(nx) + " " + to_string(ny)];
int len = s.size();
for(int j = 0;j<len;j++)
{
if(s[j] == ' ')
{
mid = j;
break;
}
}
dfs(stoi(s.substr(0,mid)),stoi(s.substr(mid+1,len)),t+1);
vis[nx][ny] = 0;
}
else
{
vis[nx][ny] = 1;
dfs(nx,ny,t + 1);
vis[nx][ny] = 0;
}
}
}
return 0;
}
int main()
{
cin >> n >> m;
memset(jiyi,0x3f,sizeof(jiyi));
for(int i = 0;i<n;i++)
{
for(int j = 0;j<m;j++)
{
cin >> mp[i][j];
if(mp[i][j] == '@')
{
sx = i;sy = j;
}
if(mp[i][j] >= 'A' && mp[i][j] <= 'Z' && tong[mp[i][j] - 'A'] == "")
{
if(i == 0 && j != 0)
{
tong[mp[i][j] - 'A'] = "0 " + to_string(j);
continue;
}
if(i != 0 && j == 0)
{
tong[mp[i][j] - 'A'] = to_string(i) + " 0";
continue;
}
if(i == 0 && j == 0)
{
tong[mp[i][j] - 'A'] = "0 0";
continue;
}
tong[mp[i][j] - 'A'] = to_string(i) + " " + to_string(j);
}
else if(mp[i][j] >= 'A' && mp[i][j] <= 'Z' && tong[mp[i][j] - 'A'] != "")
{
if(i == 0 && j != 0)
{
conveyor[tong[mp[i][j] - 'A']] = "0 " + to_string(j);
conveyor["0 " + to_string(j)] = tong[mp[i][j] - 'A'];
continue;
}
if(i != 0 && j == 0)
{
conveyor[tong[mp[i][j] - 'A']] = to_string(i) + " 0";
conveyor[to_string(i) + " 0"] = tong[mp[i][j] - 'A'];
continue;
}
if(i == 0 && j == 0)
{
conveyor[tong[mp[i][j] - 'A']] = "0 0";
conveyor["0 0"] = tong[mp[i][j] - 'A'];
continue;
}
conveyor[tong[mp[i][j] - 'A']] = to_string(i) + " " + to_string(j);
conveyor[to_string(i) + " " + to_string(j)] = tong[mp[i][j] - 'A'];
}
}
}
dfs(sx,sy,0);
cout << ans << endl;
return 0;
}
我知道是搜索中的那个for循环害的,TLE了#13和#15 点,但我记录那个mid后出现各种错误,所以大犇们快来帮忙优化一下,谢谢了!