提供spj
查看原帖
提供spj
553625
scp020楼主2024/1/4 15:14

测试过样例,没有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;
}
2024/1/4 15:14
加载中...