捞一手远古帖子，我改进了传送门查找方法，用数组直接预处理。分数不变
by zhongshizhao1 @ 2023-07-19 16:13:26
```cpp
#include <iostream>
#include <cstring>
using namespace std;
int n,m,zx,zy,smax=1000000,sum=0;
int movei=-1,movej=-1;
char a[505][505];
int bz[505][505];
int f[505][505];
int csm[26][4];
int dx[4]={0,1,0,-1},
dy[4]={1,0,-1,0};
bool flag=0;
void dfs(int p,int q)
{
int x,y;
if(sum>=f[p][q]&&(a[p][q]<'A'||a[p][q]>'Z'))
{
return;
}
if(a[p][q]<'A'||a[p][q]>'Z')
{
f[p][q]=sum;
}
if(a[p][q]<'A'||a[p][q]>'Z')
{
bz[p][q]=1;
}
if(p==zx&&q==zy)
{
if(sum<smax)
{
smax=sum;
}
return;
}
for(int i=0;i<4;i++)
{
x=p+dx[i];
y=q+dy[i];
if(x>=0&&x<n&&y>=0&&y<m&&bz[x][y]==0&&a[x][y]!='#')
{
sum++;
if(a[x][y]>='A'&&a[x][y]<='Z')
{
int t=a[x][y]-'A';
if(csm[t][2]==-1)
{
bz[x][y]=1;
dfs(x,y);
bz[x][y]=0;
sum--;
}
else if(csm[t][0]==x&&csm[t][1]==y)
{
bz[x][y]=1;
dfs(csm[t][2],csm[t][3]);
bz[x][y]=0;
sum--;
}
else
{
bz[x][y]=1;
dfs(csm[t][0],csm[t][1]);
bz[x][y]=0;
sum--;
}
}
else
{
dfs(x,y);
bz[x][y]=0;
sum--;
}
}
}
}
int main()
{
int sx,sy,ji=0;
memset(f,0xaa7f,sizeof(f));
memset(csm,-1,sizeof(csm));
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
if(a[i][j]=='@')
{
sx=i;
sy=j;
}
else if(a[i][j]=='=')
{
zx=i;
zy=j;
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]>='A'&&a[i][j]<='Z')
{
int t=a[i][j]-'A';
if(csm[t][0]==-1)
{
csm[t][0]=i;
csm[t][1]=j;
}
else
{
csm[t][2]=i;
csm[t][3]=j;
}
}
}
}
dfs(sx,sy);
cout<<smax<<endl;
return 0;
}
```
by zhongshizhao1 @ 2023-07-19 16:14:32
有没有dalao用深搜AC的，麻烦指教一下
by zhongshizhao1 @ 2023-07-19 16:15:14
https://www.luogu.com.cn/record/117532587
```
#include <bits/stdc++.h>
using namespace std;
const int N = 301;
char g[N][N];
bool vis[N][N], f = 0;
int n, m, sx, sy, ex, ey, dx[5] = {-1, 0, 1, 0}, dy[5] = {0, 1, 0, -1};
struct Node {
int x, y, step;
};
queue<Node> que;
void get_idx(int &x1, int &y1) {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (g[i][j] == g[x1][y1] && (i != x1 || j != y1)) {
x1 = i, y1 = j;
return;
}
}
}
void bfs(int x, int y) {
que.push({x, y, 0});
vis[x][y] = 1;
while (!que.empty()) {
Node t = que.front();
que.pop();
if (g[t.x][t.y] >= 'A' && g[t.x][t.y] <= 'Z') {
get_idx(t.x, t.y);
}
for (int i = 0; i < 4; i++) {
int xx = t.x + dx[i];
int yy = t.y + dy[i];
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && g[xx][yy] != '#' && vis[xx][yy] == 0) {
vis[xx][yy] = 1;
que.push({xx, yy, t.step + 1});
}
if (g[xx][yy] == '=') {
f = 1;
break;
}
}
if (f) break;
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
if (g[i][j] == '@') {
sx = i;
sy = j;
}
}
}
bfs(sx, sy);
cout << que.back().step << endl;
return 0;
}
```
by wsm19807498692 @ 2023-07-26 16:07:22