当前位置：首页 > news >正文

B3791 [信息与未来 2023] 电路布线

news 2025/4/28 17:01:03

一、题目情况

这道题目的题目情况是这样的：

众所周知，动态规划+搜索这玩意不是给人做的，所以——

我的代码（草履虫版），应运而生——

并且，成功拿到了——

85分（考场17pts）。

二、得分情况

三、评分标准

在你的布线方案合法（连通且无回路）的前提下：

如果你的方案是最优布线方案，即布线的格子最多，该测试点得满分。
否则，该测试点得一半分数。

本题原始满分为 20pts。

四、得分情况

我的得分情况：7AC+3WA(50%分数)

7*10+3*5=70+15=85(pts)=17(考场pts)

五、具体思路

现在是具体思路。

省赛最后一题最常出：模拟、大数据、人工智能、贪心、最优解等题目。

首先需要知道的是，2023年这一题无论是拿满分的搜索动归还是拿大分的模拟，都有相当可观的代码量，且思路复杂，细节较多，需要预留较多的时间。

对于 100% 的数据，满足 1≤n,m≤6。

所以，大规模的递归和 $n^3$ 的循环完全可以接受。

以下展示了一种合法和两种不合法的布线方案：

#+.+.# #.+..# #++..#
+++++# ..+++# .++++#
.+#### .+#### .+####
.++++# .+...# .+...#
合法 不连通 有回路

代码最大的难点就在于对合法与最优解的判断。

怎么办呢？

以下是具体步骤——

1.将所有点全部变成"+"

         "#">>-1; 不能改动
          "+">>0 ; 不能改动
         ".">>1 ; 可以改动，需要判断回路问题

2.判断可以删除的"+"，（有回路问题）

3.判断可以增加的"+"。

规则：

1.原数组，不进行改变
2.设置2个数组
3.数字全部设置成字符，不要变成数字，会增加代码复杂度

对于回路问题的判断：

1.建立t数组，初始赋值0
2.递归四方向遍历查找
规则:
1.如果碰到-1,返回false
2.只要某函数出现返回false的情况，之后的所有函数都是false。
3.记录上一次函数所使用的方向
4.如果在与上一次函数所使用方向不矛盾的情况下仍遇到了-1则返回false。
x y
1 | 0 右
-1| 0 左
0 | 1 下
0 | -1 上
85pts（考场=85*0.2=17分）蓝题

#include <bits/stdc++.h>
using namespace std;
//常用变量
int n,m;
char y[10][10]; 
char b[10][10];
int dx[5]={1,-1,0,0};
int dy[5]={0,0,1,-1};
//局部变量 
int S;
int t[10][10];
bool Err(int x,int y,int last,int sh)//判断回路问题
{//模板t[x][y]=0;sh--;if(sh==0) return 0;for(int i=0; i<4; i++){if((i==0&&last==1)||(i==1&&last==0)||(i==2&&last==3)||(i==3&&last==2)) continue;int lx=x+dx[i];int ly=y+dy[i];if(lx<1||lx>n||ly<1||ly>m) continue;else if(b[lx][ly]=='+'){if(t[lx][ly]==0) return 1;else if(Err(lx,ly,i,sh)==1) return 1;}}return 0;
}
void out()//输出
{for(int i=1; i<=n; i++){for(int j=1; j<=m; j++) cout<<b[i][j];cout<<'\n';}
}
void go()//刚开始的删除，不合法就删
{for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){memset(t,-1,sizeof(t));int ans=Err(i,j,-1,S);if(y[i][j]=='.'&&ans==1){b[i][j]='.';S--;}/*out();for(int i=1; i<=n; i++){for(int j=1; j<=m; j++) cout<<setw(2)<<t[i][j];cout<<'\n';}cout<<'\n';system("pause");*/}}
}
void more()//再遍历一次，增加还能加上的地方
{for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){if(y[i][j]=='.'&&b[i][j]=='.'){b[i][j]='+';S++;memset(t,-1,sizeof(t));int ans=Err(i,j,-1,S);if(ans==1){b[i][j]='.';S--;}}}}
}
int 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>>y[i][j];b[i][j]=y[i][j];if(b[i][j]=='.') b[i][j]='+';if(b[i][j]=='+') S++;}}go();more();out();return 0;
}

#include <bits/stdc++.h>
using namespace std;
//常用变量
int n,m;
char y[10][10];
char b[10][10];
int dx[5]={1,-1,0,0};
int dy[5]={0,0,1,-1};
//局部变量
int S;
int t[10][10];
bool Err(int x,int y,int last,int sh)
{
   t[x][y]=0;
   sh--;
   if(sh==0) return 0;
   for(int i=0; i<4; i++)
   {
       if((i==0&&last==1)||(i==1&&last==0)||(i==2&&last==3)||(i==3&&last==2)) continue;
       int lx=x+dx[i];
       int ly=y+dy[i];
       if(lx<1||lx>n||ly<1||ly>m) continue;
       else if(b[lx][ly]=='+')
       {
           if(t[lx][ly]==0) return 1;
           else if(Err(lx,ly,i,sh)==1) return 1;
       }
   }
   return 0;
}
void out()
{
   for(int i=1; i<=n; i++)
   {
       for(int j=1; j<=m; j++) cout<<b[i][j];
       cout<<'\n';
   }
}
void go()
{
   for(int i=1; i<=n; i++)
   {
       for(int j=1; j<=m; j++)
       {
           memset(t,-1,sizeof(t));
           int ans=Err(i,j,-1,S);
           if(y[i][j]=='.'&&ans==1)
           {
               b[i][j]='.';
               S--;
           }
           /*
           out();
           for(int i=1; i<=n; i++)
           {
               for(int j=1; j<=m; j++) cout<<setw(2)<<t[i][j];
               cout<<'\n';
           }
           cout<<'\n';
           system("pause");
           */
       }
   }
}
void more()
{
   for(int i=1; i<=n; i++)
   {
       for(int j=1; j<=m; j++)
       {
           if(y[i][j]=='.'&&b[i][j]=='.')
           {
               b[i][j]='+';
               S++;
               memset(t,-1,sizeof(t));
               int ans=Err(i,j,-1,S);
               if(ans==1)
               {
                   b[i][j]='.';
                   S--;
               }
           }
       }
   }
}
int 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>>y[i][j];
           b[i][j]=y[i][j];
           if(b[i][j]=='.') b[i][j]='+';
           if(b[i][j]=='+') S++;
       }
   }
   go();
   more();
   out();
   return 0;
}