北岭山脚鼠鼠 2022-05-20 17:32 采纳率: 0%
浏览 11
已结题

Cleaning Robot改了很久都过不去


#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
const int N=110;
typedef pair<int,int>PII;
long long ans;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int n,m;
int idx;
char d[N][N];
int dist[N][N];
int ju[N][N];
int biao[N][N];
bool st[N][N];
struct nod
{
    int x,y;
};
nod node[25];
void bfs(int x,int y)
{
    memset(ju,-1,sizeof ju);
   dist[biao[x][y]][biao[x][y]]=0;
    ju[x][y]=0;
    queue<nod>que;
    que.push({x,y});
while(que.size())
{
    nod t=que.front();
    que.pop();

    for(int i=0;i<4;i++)
    {
        int x1=t.x+dx[i],y1=t.y+dy[i];
        if(ju[x1][y1]==-1&&(d[x1][y1]=='.'||d[x1][y1]=='o'||d[x1][y1]=='*')&&x1>=1&&x1<=n&&y1>=1&&y1<=m)
        {
            ju[x1][y1]=ju[t.x][t.y]+1;
            que.push({x1,y1});
            if( dist[biao[x][y]][biao[x1][y1]]==-1&&(d[x1][y1]=='*'||d[x1][y1]=='o'))
            {
                //d[x1][y1]='.';
                //cout<<x<<' '<<y<<' '<<x1<<' '<<y1<<endl;
                dist[biao[x][y]][biao[x1][y1]]=ju[x1][y1];
                 dist[biao[x1][y1]][biao[x][y]]=ju[x1][y1];
            }
        }
    }
}
}
void dfs(long long sum,int num,int op)
{
    if(op==idx)
    {
        //cout<<idx<<endl;
        ans=min(ans,sum);
    //cout<<endl;
    return;
    }
        if(sum>ans)return;
    for(int i=2;i<=idx;i++)
    {
        if(dist[num][i]!=-1&&num!=i&&st[i][num]==0)
        {
            st[i][num]=1;
        st[num][i]=1;
         //cout<<num<<' '<<i<<endl;
        dfs(sum+dist[num][i],i,op+1);
        st[i][num]=0;
        st[num][i]=0;
        }
    }
    return;
}

int main() {
   while(scanf("%d%d",&m,&n)!=EOF&&n&&m)
   {
       memset(dist,-1,sizeof dist);
       ans=0x3f3f3f3f3f;
        idx=2;
       for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
       {
        cin>>d[i][j];
        if(d[i][j]=='o')
        {
            node[1].x=i;
            node[1].y=j;
           biao[i][j]=1;
        }else if(d[i][j]=='*')
        {
            node[idx].x=i;
            node[idx].y=j;
            biao[i][j]=idx;
            ++idx;
        }
       }
       idx--;

       for(int i=1;i<=idx;i++)
       {
           bfs(node[i].x,node[i].y);
       }

       bool flag=0;
       for(int i=1;i<=idx;i++)
        for(int j=i+1;j<=idx;j++)
        if(dist[i][j]==-1)
       {
           flag=1;
       }
       if(flag)
       {
           cout<<-1<<endl;
           continue;
       }
       memset(st,0,sizeof st);
       dfs(0,1,1);
       cout<<ans<<endl;
   }
        return 0;
}
  • 写回答

0条回答 默认 最新

    报告相同问题?

    问题事件

    • 系统已结题 5月28日
    • 创建了问题 5月20日

    悬赏问题

    • ¥15 对于相关问题的求解与代码
    • ¥15 ubuntu子系统密码忘记
    • ¥15 信号傅里叶变换在matlab上遇到的小问题请求帮助
    • ¥15 保护模式-系统加载-段寄存器
    • ¥15 电脑桌面设定一个区域禁止鼠标操作
    • ¥15 求NPF226060磁芯的详细资料
    • ¥15 使用R语言marginaleffects包进行边际效应图绘制
    • ¥20 usb设备兼容性问题
    • ¥15 错误(10048): “调用exui内部功能”库命令的参数“参数4”不能接受空数据。怎么解决啊
    • ¥15 安装svn网络有问题怎么办