蒟蒻记忆化dfs86分求助,大犇们帮忙看看,谢谢了
查看原帖
蒟蒻记忆化dfs86分求助,大犇们帮忙看看,谢谢了
932569
I_AM_Nigger楼主2023/7/1 23:40
#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后出现各种错误,所以大犇们快来帮忙优化一下,谢谢了!

2023/7/1 23:40
加载中...