测试过样例,没有bug,希望管理员进一步检验spj的正确性
#include<bits/stdc++.h>
#include "testlib.h"
int n,m,col[10][10];
int dx[]={0,0,1,0,-1};
int dy[]={0,1,0,-1,0};
char ori[10][10],answ[10][10],given[10][10];
bool flag;
inline bool check1() noexcept
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(ori[i][j]=='#' || ori[i][j]=='+') if(ori[i][j]!=given[i][j]) return false;
return true;
}
inline bool check2() noexcept
{
bool flag=false;
int cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(given[i][j]=='+')
{
cnt++;
for(int k=1;k<=4;k++) if(given[i+dx[k]][j+dy[k]]=='+') flag=true;
}
return flag || cnt==1;
}
inline int check3() noexcept
{
int cnt1=0,cnt2=0;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cnt1+=answ[i][j]=='+',cnt2+=given[i][j]=='+';
if(cnt1==cnt2) return 1; // 最优
if(cnt1>cnt2) return 2; // 满足条件但是不优
return 3; // 答案不是最优
}
inline void dfs(int x,int y,int fx,int fy)
{
if(x<0 || x>n || y<0 || y>m || flag) return;
col[x][y]=1;
for(int i=1;i<=4;i++)
{
if(x+dx[i]==fx && y+dy[i]==fy || x+dx[i]<0 || x+dx[i]>n || y+dy[i]<0 || y+dy[i]>m) continue;
if(given[x+dx[i]][y+dy[i]]!='+') continue;
if(col[x+dx[i]][y+dy[i]]==1)
{
flag=true;
return;
}
if(!col[x+dx[i]][y+dy[i]]) dfs(x+dx[i],y+dy[i],x,y);
}
col[x][y]=2;
}
inline bool inrange(const char &ch)
{
if(ch=='#' || ch=='+' || ch=='.') return true;
return false;
}
int main(int argc,char* argv[])
{
registerTestlibCmd(argc,argv);
n=inf.readInt(),m=inf.readInt();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
ori[i][j]=inf.readChar();
while(!inrange(ori[i][j])) ori[i][j]=inf.readChar();
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
answ[i][j]=ans.readChar();
while(!inrange(answ[i][j])) answ[i][j]=ans.readChar();
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
given[i][j]=ouf.readChar();
while(!inrange(given[i][j])) given[i][j]=ouf.readChar();
}
if(!check1()) quitf(_wa,"The answer is wrong: the answer is unconventional"); // 改变了不能布线的格子和必须布线的格子
if(!check2()) quitf(_wa,"The answer is wrong: the answer is unconventional"); // 不连通
bool fl=true;
for(int i=1;i<=n && fl;i++)
for(int j=1;j<=m && fl;j++)
if(given[i][j]=='+') dfs(i,j,0,0),fl=false;
if(flag) quitf(_wa,"The answer is wrong: the answer is unconventional"); // 有环
int res=check3();
if(res==1) quitf(_ok,"The answer is correct.");
else if(res==2) quitp(0.5,"The answer is not the best solution");
else quitf(_fail,"The model answer is not the best solution");
return 0;
}