SeventhExper.zip

#include <iostream> #include <conio.h> #include <chrono> using namespace std; #define MAX 50 int m,n;//行数和列数 int Monitor[MAX+2][MAX+2]={0};//记录该位置是否被监控 int Guard[MAX+2][MAX+2]={0};//记录该位置是否有哨兵 int best;//最优哨兵数 int B;//当前哨兵数 int i=1,j=1;//控制位置从（1,1）开始 int kind=0;//记录最优解的个数 struct{int m[MAX+2][MAX+2];}T[MAX*MAX];//保存最优解 void Backtrack()//回溯 { while(i*j>1 && Guard[i][j]==1) { if(j==1) {i--;j=n;} else j--; } if(Guard[i][j]==0) { Guard[i][j]=1; Monitor[i][j]++; Monitor[i-1][j]++; Monitor[i][j-1]++; Monitor[i][j+1]++; Monitor[i+1][j]++; B++; if(j==n) { if(i==m) j++; else {j=1;i++;} } else j++; } } void Output()//输出 { cout<<"一共有"<<kind+1<<"种最优方案"<<endl; cout<<"最优哨兵数为："<<best<<endl; for(int i=0;i<=kind;i++) { cout<<"第"<<i+1<<"种"<<endl; for(int j=1;j<=m;j++) { for(int k=1;k<=n;k++) { cout<<T[i].m[j][k]<<" "; } cout<<endl; } cout<<endl; } } void Cancelguard()//取消哨兵 { Guard[i][j]=0; Monitor[i][j]--; Monitor[i-1][j]--; Monitor[i+1][j]--; Monitor[i][j-1]--; Monitor[i][j+1]--; } void Run() { while(1) { while(i*j<=n*m) { if(i==m) { if(Monitor[i][j]-1!=0 && Monitor[i-1][j]-1!=0 && Monitor[i+1][j]-1!=0 && Monitor[i][j-1]-1!=0 && Monitor[i][j+1]-1!=0) { Cancelguard();j++;B--; } else { j++; } } else { if(Monitor[i][j]-1!=0 && Monitor[i-1][j]-1!=0 && Monitor[i+1][j]-1!=0 && Monitor[i][j-1]-1!=0 && Monitor[i][j+1]-1!=0) { Cancelguard(); if(j==n) {j = 1;i++;} else j++; B--; } else { if(j==n) {j = 1;i++;} else j++; } } } if(B<best) { best=B;kind=0; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) {T[kind].m[i][j]=Guard[i][j];} } } else if(B==best) { kind++; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) {T[kind].m[i][j]=Guard[i][j];} } } j--; Backtrack(); if(i==1 && j==1) break; } } int main() { cout<<"请输入陈列馆的行数和列数m,n："; cin>>m>>n; B=m*n;best=m*n/3+2; for(int i=1;i<=m;i++) for (int j=1;j<=n;j++) { Guard[i][j]=1; Monitor[i][j]++; Monitor[i-1][j]++; Monitor[i][j-1]++; Monitor[i][j+1]++; Monitor[i+1][j]++; } for (int j=0;j<=n+1;j++) { Monitor[0][j]=2; Monitor[m+1][j]=2; } for (int i=0;i<=m+1;i++) { Monitor[i][0]=2; Monitor[i][n+1]=2; } auto start = std::chrono::steady_clock::now(); Run(); auto end = std::chrono::steady_clock::now(); std::chrono::duration <double, std::micro> elapsed=end-start; std::cout<< "主算法运行时间（微秒）: "<<elapsed.count()<< "us" <<std::endl; Output(); getch(); return 0; }