记录详情

Accepted


  
正在同步测试数据,请稍后
[Hydro](https://hydro.ac)提供评测服务
# 状态 耗时 内存占用
#1 Accepted 7ms 2.277 MiB
#2 Accepted 9ms 2.402 MiB
#3 Accepted 7ms 2.402 MiB
#4 Accepted 8ms 2.402 MiB

代码

//
//  main.cpp
//  2
//
//  Created by 汪汪队 on 2023/7/8.
//

#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 505;
int n,m;
char G[N][N];
int dis[N][N];
int vis[N][N];
int ans=0;
int fx[]={0,0,1,-1};
int fy[]={1,-1,0,0};

void dfs(int topx,int topy,int fruit){
    if(topx==n&&topy==m){
        if(G[n][m]=='#') fruit++;
        ans=max(ans,fruit);
        return;
    }
    else{
        vis[topx][topy]=1;
        for (int i=0; i<4; i++) {
            int xx=topx+fx[i];
            int yy=topy+fy[i];
            if(xx<1||yy<1||xx>n||yy>m||G[xx][yy]=='1'||vis[xx][yy])
                continue;
            else{
                if(G[xx][yy]=='#'){
                    vis[xx][yy]=1;
                    dfs(xx, yy, fruit+1);
                    vis[xx][yy]=0;
                }
                else{
                    vis[xx][yy]=1;
                    dfs(xx, yy, fruit);
                    vis[xx][yy]=0;
                }
            }
        }
        vis[topx][topy]=0;
    }
    return;
}

void bfs(){
    queue<pair<int,int>>q;
    q.push({1,1});
    dis[1][1]=0;
    while (q.size()) {
        int topx=q.front().first;
        int topy=q.front().second;
        q.pop();
        for (int i=0; i<4; i++) {
            int xx=topx+fx[i];
            int yy=topy+fy[i];
            if(xx<1||yy<1||xx>n||yy>m||dis[xx][yy]<=dis[topx][topy]+1||G[xx][yy]=='1')
                continue;
            else{
                dis[xx][yy]=dis[topx][topy]+1;
                q.push({xx,yy});
            }
        }
    }
    return;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin>>n>>m;
    
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            cin>>G[i][j];
            dis[i][j]=0x3f3f3f3f;
        }
    }
    
    bfs();
    
    cout<<dis[n][m]<<" ";
    
    memset(vis, 0, sizeof(vis));
    
    dfs(1,1,0);
    
    cout<<ans<<endl;
    
    return 0;
}

//ans=2;

信息

递交者
类型
递交
题目
P1015 6 营救公主
语言
C++
递交时间
2023-07-08 16:43:47
评测时间
2023-12-12 14:57:55
评测机
分数
100
总耗时
33ms
峰值内存
2.402 MiB