爆搜！爆搜！爆搜！爆搜！爆搜！
先看题目题目描述
在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。● ○ ●
○ ● ○ ●
● ○ ● ○
○ ● ○
输入输出格式
输入格式： 从文件中读入一个4*4的初始棋局，黑棋子用B表示，白棋子用W表示，空格地带用O表示。输出格式：
用最少的步数移动到目标棋局的步数。输入输出样例
输入样例#1： BWBO WBWB BWBW WBWO 输出样例#1： 5乍一看，肯定是搜索，应该要剪枝，不剪枝时间上恐怕过不去，这怎么做，没思路，不会，我太弱了，我怎么这么弱，自闭。。。
仔细想想，直接dfs会怎样，怎么样也会骗点分吧，（嗯，这题可做）扶我起来，我还要打代码！！！再仔细想想每次每个空格周围有4种走法，所以最多也就8种走法，4*4的棋盘，好像完全可以，(不能自闭，站起来A了这题！！！)，当走14次的时候就会遍历了整个棋盘，所以总步数不会超过14？？？还可以优化？，开敲！敲完后，满心欢喜地测样例，却发现过不了样例，这就很尴尬，实在没办法了，问学长吧，然后“一语惊醒梦中人”，黑白棋要交替下的！！！所以，记录下移动的棋的颜色，下一次走的时候不走这种颜色的就可以了。
（看来遇到问题要多想想，不能自闭）。贴代码：
#include#include #include using namespace std;char pic[5][5];int ans = 2147483647;int tx[9] = {0,1,-1,0,0};int ty[9] = {0,0,0,1,-1};//最原始判断方法int check(){ if(pic[1][1] == pic[1][2] && pic[1][2] == pic[1][3] && pic[1][3] == pic[1][4])return 1; if(pic[2][1] == pic[2][2] && pic[2][2] == pic[2][3] && pic[2][3] == pic[2][4])return 1; if(pic[3][1] == pic[3][2] && pic[3][2] == pic[3][3] && pic[3][3] == pic[3][4])return 1; if(pic[4][1] == pic[4][2] && pic[4][2] == pic[4][3] && pic[4][3] == pic[4][4])return 1; if(pic[1][1] == pic[2][1] && pic[2][1] == pic[3][1] && pic[3][1] == pic[4][1])return 1; if(pic[1][2] == pic[2][2] && pic[2][2] == pic[3][2] && pic[3][2] == pic[4][2])return 1; if(pic[1][3] == pic[2][3] && pic[2][3] == pic[3][3] && pic[3][3] == pic[4][3])return 1; if(pic[1][4] == pic[2][4] && pic[2][4] == pic[3][4] && pic[3][4] == pic[4][4])return 1; if(pic[1][1] == pic[2][2] && pic[2][2] == pic[3][3] && pic[3][3] == pic[4][4])return 1; if(pic[1][4] == pic[2][3] && pic[2][3] == pic[3][2] && pic[3][2] == pic[4][1])return 1; return 0;}void dfs(int t,char opt){ if(t > ans ||t > 14)return;//剪枝优化 if(check()){ ans = min(ans,t); return; } for(int i = 1; i<=4; i++){ for(int j = 1; j<=4; j++){ if(pic[i][j] == 'O'){ for(int k = 1; k<=4; k++){ int dx,dy; dx = i + tx[k]; dy = j + ty[k]; if(dx <= 4 && dx >=1 && dy <= 4 && dy >= 1 &&pic[dx][dy] != opt&& pic[dx][dy] != 'O'){ swap(pic[dx][dy],pic[i][j]);//cout< <<' '< <<'\n'; //cout< << ' ' << j << '\n'; dfs(t + 1,pic[i][j]);//传的是移动步数，和该步所移动棋子的颜色 swap(pic[dx][dy],pic[i][j]); } } } } } return;}int main(){ for(int i = 1; i<=4; i++){ for(int j = 1; j<=4; j++){ cin >> pic[i][j]; } } if(check()){ cout<<1<<'\n'; return 0; } dfs(0,'O'); //if(ans == 1)ans = 0; cout << ans; return 0;}