AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

洛谷P1825 玉米迷宫 dfs过了86分,wa6和wa8,求佬佬调!

作者: 作者的头像   当下LYC ,  2024-11-03 13:14:19 ,  所有人可见 ,  阅读 11


3


#include <bits/stdc++.h>
using namespace std;
int n,m,ans = 0x3f3f3f3f,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},st[305][305],dis[305][305];
char w[305][305],c;
using pii = pair<int,int>;
pii sr,ed,o;
map<char,pair<pii,pii>> mp;//两个坐标比对 
void dfs(int x,int y,int t) 
{
    if(w[x][y]=='=') {ans=min(t,ans);return;}
    if(w[x][y]>='A'&&w[x][y]<='Z') {
        int nx=x,ny=y;char cc = w[nx][ny];//变项与不变项 
        if((nx==mp[cc].first.first)&&(ny==mp[cc].first.second)) 
            x=mp[cc].second.first,y=mp[cc].second.second;
        else x=mp[cc].first.first,y=mp[cc].first.second;
    }
    for(int i = 0 ; i <= 3 ; i++) {
        int xx = x+dx[i],yy=y+dy[i];
        if(dis[xx][yy]<=t+1) continue;
        dis[xx][yy]=t+1;
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&w[xx][yy]!='#'&&!st[xx][yy]){ 
            st[xx][yy]=true;
            dfs(xx,yy,t+1);
            st[xx][yy]=false;
        }
    }
    return; 
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);  
    cin >> n >> m;
    o={0,0}; 
    memset(dis,0x3f,sizeof dis);
    for(int i = 1 ; i <= n ; i++) {
        for(int j = 1 ; j <= m ; j++) {
            cin >> w[i][j];
            if(w[i][j]=='@') sr={i,j};
            else if((w[i][j]>='A')&&(w[i][j]<='Z')) 
                if(mp[w[i][j]].first==o) mp[w[i][j]].first={i,j};
                else mp[w[i][j]].second = {i,j};
        }
    }
    st[sr.first][sr.second]=1;
    dis[sr.first][sr.second]=0;//到这个点所需要的时间 
    dfs(sr.first,sr.second,0);
    cout << ans << endl;
    return 0;
}

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息