DFS超时
查看原帖
DFS超时
295602
奈因楼主2020/6/28 22:20
#include <bits/stdc++.h>
using namespace std;
bool flag[4][4];
int step=0x7ffffff;
int kx1[5]={0,1,-1,0,0};
int ky1[5]={0,0,0,1,-1};
void dfs(int x,int y,int step1)
{if(flag[1][1]==true&&flag[1][2]==true&&flag[1][3]==true&&flag[2][1]==true&&flag[2][2]==true&&flag[2][3]==true&&flag[3][1]==true&&flag[3][2]==true&&flag[3][3]==true)
{
	step=min(step,step1);
	return;
}
	else if(step1<=step)
	{
	for(int i=0;i<=4;i++)
	{
	int kx=x+kx1[i];
	int ky=y+ky1[i];
	if(kx>0&&ky>0&&kx<4&&ky<4)
	{
	 flag[kx][ky]=1-flag[kx][ky];
         if(x+1!=4&&y+1!=4)
        {
             	dfs(x,y+1,step1+1);
        }
	else
	{
	y=1;
	dfs(x+1,y,step1+1);
	}
	flag[kx][ky]=1-flag[kx][ky];
	}
	}
}
}
int loading()
{
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++)
		{
			cin>>flag[i][j];
		}
	}
}
int main()
{
    loading();
    dfs(1,1,0);
    cout<<step;
    return 0;
}

2020/6/28 22:20
加载中...