妹子刚学OI简单模拟题WA#25求调(玄关)
查看原帖
妹子刚学OI简单模拟题WA#25求调(玄关)
556545
_anll_楼主2024/7/8 19:01

rt,WA#25,实在不知道为什么了,求dalao捞捞QAQ!

#include<unordered_map>
#include<iostream>
#include<vector>
#include<map>
#define C 5201413
#define int long long
using namespace std;
const int N=4e5+5;
int n,m,cnt,tot,ans,px,py,pos[5][2]={{+1,0},{-1,0},{0,+1},{0,-1},{0,0}};
vector<int> mp[N],vo[N];
map<pair<pair<int,int>,pair<int,int> >,int> vu;
bool ch(int x,int y){
	if(x<1||x>n||y<1||y>m) return 0;
	return 1;
}
bool check1(int x,int y){
	if(!ch(x,y)) return 1;
	for(int i=0;i<4;i++){
		int xx=x+pos[i][0],yy=y+pos[i][1];
		if(!ch(xx,yy)) continue;
		if(mp[xx][yy]<mp[x][y]) return 1;
	}
	return 0;
}
void check2(int a,int b,int x,int y){
	int xx,yy,tot1=0,tot2=0;
	if(!ch(x,y)) return;
	for(int i=0;i<5;i++){
		xx=x+pos[i][0],yy=y+pos[i][1];
		if(vo[xx][yy]) continue;
		vo[xx][yy]=1;
		if(!check1(xx,yy)) tot1++;
		
		xx=a+pos[i][0],yy=b+pos[i][1];
		if(vo[xx][yy]) continue;
		vo[xx][yy]=1;
		if(!check1(xx,yy)) tot1++;
	}
	for(int i=0;i<5;i++){
		xx=x+pos[i][0],yy=y+pos[i][1];
		vo[xx][yy]=0;
		xx=a+pos[i][0],yy=b+pos[i][1];
		vo[xx][yy]=0;
	}
	swap(mp[a][b],mp[x][y]);
	for(int i=0;i<5;i++){
		xx=x+pos[i][0],yy=y+pos[i][1];
		if(vo[xx][yy]) continue;
		vo[xx][yy]=1;
		if(!check1(xx,yy)) tot2++;
		
		xx=a+pos[i][0],yy=b+pos[i][1];
		if(vo[xx][yy]) continue;
		vo[xx][yy]=1;
		if(!check1(xx,yy)) tot2++;
	}
	if(cnt-(tot1-tot2)==0&&!vu[{{a,b},{x,y}}]){
		vu[{{a,b},{x,y}}]=vu[{{x,y},{a,b}}]=1;
		ans++;
	}
	swap(mp[a][b],mp[x][y]);
	for(int i=0;i<5;i++){
		xx=x+pos[i][0],yy=y+pos[i][1];
		vo[xx][yy]=0;
		xx=a+pos[i][0],yy=b+pos[i][1];
		vo[xx][yy]=0;
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;int awa;
	for(int i=1;i<=n;i++){
		mp[i].push_back(0);vo[i].push_back(0);
		for(int j=1;j<=m;j++){
			cin>>awa;
			mp[i].push_back(awa);vo[i].push_back(0);
		}
		vo[i].push_back(0);
	}
	for(int i=0;i<=m+1;i++) vo[0].push_back(0);
	for(int i=0;i<=m+1;i++) vo[n+1].push_back(0);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
		if(!check1(i,j)&&mp[i][j]!=1) cnt++,px=i,py=j;
	if(!cnt){cout<<0;return 0;}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=0;k<5;k++){
				check2(i,j,px+pos[k][0],py+pos[k][1]);
			}
		}
	}
	if(ans) cout<<"1 "<<ans;
	else cout<<2;
	return 0;
}
2024/7/8 19:01
加载中...