蒟蒻60分WA求助
  • 板块P2346 四子连棋
  • 楼主cyfff
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/10/27 11:03
  • 上次更新2023/11/5 09:46:06
查看原帖
蒟蒻60分WA求助
181437
cyfff楼主2020/10/27 11:03
#include<bits/stdc++.h>
using namespace std;
int a[10][10],ans,fx[5]={-1,1,0,0},fy[5]={0,0,-1,1},i,j,r1,c1,r2,c2;char c;
int ck(){
	for(i=1;i<5;++i)
    if((a[i][1]==a[i][2]&&a[i][2]==a[i][3]&&a[i][3]==a[i][4])||
	(a[1][i]==a[2][i]&&a[2][i]==a[3][i]&&a[3][i]==a[4][i]))return 1;
    if((a[1][1]==a[2][2]&&a[2][2]==a[3][3]&&a[3][3]==a[4][4])||
	(a[1][4]==a[2][3]&&a[2][3]==a[3][2]&&a[3][2]==a[4][1]))return 1;
    return 0;
}
int dfs(int x,int y,int X,int Y,int nw,int st){
	if(ans==st)return ck();
	for(int k=0,dx,dy,dX,dY;k<4;++k){
		dx=fx[k]+x;dy=fy[k]+y;
		dX=fx[k]+X;dY=fy[k]+Y;
		if(dx>0&&dx<5&&dy>0&&dy<5&&a[dx][dy]!=nw){
			swap(a[x][y],a[dx][dy]);
			if(dfs(dx,dy,X,Y,(nw&1)+1,st+1))return 1;
			swap(a[dx][dy],a[x][y]);
		}
		if(dX>0&&dX<5&&dY>0&&dY<5&&a[dY][dY]!=nw){
			swap(a[X][Y],a[dX][dY]);
			if(dfs(x,y,dX,dY,(nw&1)+1,st+1))return 1;
			swap(a[dX][dY],a[X][Y]);
		}
	}
	return 0; 
}
int main(){
	for(i=1;i<5;++i)
	for(j=1;j<5;++j){
		cin>>c;
		if(c=='B')a[i][j]=1;
		else if(c=='W')a[i][j]=2;
		else if(c=='O')a[i][j]=0;
		if(!a[i][j]&&!r1)r1=i,c1=j;
        else if(!a[i][j])r2=i,c2=j;
	}
	for(ans=0;;++ans)
	if(dfs(r1,c1,r2,c2,1,0)||dfs(r1,c1,r2,c2,2,0))
	{printf("%d",ans);return 0;}
}

P2346 #2#3WA了

2020/10/27 11:03
加载中...