CodeVS/1004

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
四子连棋	★☆☆☆☆	答案正确	100	2014/12/04 19:42:46	看漏条件（45）

题意

在4*4的棋盘，黑白双方交替走棋，任意一方可以先走，求到四子连棋的最小步数。

题解

• 很明显就数据量来说，肯定是搜索题，一般来说求最小路径肯定是广搜。
• 出于偷懒，写了迭代加深搜索。和广搜类似，由于前面若干层的搜索数据量十分小，可以通过限制并且不断加大搜索深度，以此来实现类似广度优先搜索的层次遍历。
• 关于遍历：用一个delta数组来处理变化，详见5、96行。
• 判重：其实不判重也能过了（已测试，注释掉86-89行），这里判重用了3进制压位（详见getID函数）。
• 关于爆内存：好像ACM是无所谓内存的，一般来说128MB内存大概是3kw的int，6kw的short，12kw的bool，OIers特别注意下。

代码

1004.cpp代码已折叠 展开折叠内容

显示/移除行号 #include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int deltaX[4]={0,0,1,-1},deltaY[4]={1,-1,0,0}; char oC[2]={'B','W'}; class state { private: char a[5][5]; public: const bool isEnd() const { for(int i=1;i<=4;++i) { int xEnd=1,yEnd=1; for(int j=2;j<=4;++j) { if(a[j][i]!=a[j-1][i]||a[j][i]=='O') xEnd=0; if(a[i][j]!=a[i][j-1]||a[i][j]=='O') yEnd=0; } if(xEnd||yEnd) return 1; } int d1End=1,d2End=1; for(int i=2;i<=4;++i) { if(a[i][i]!=a[i-1][i-1]||a[i][i]=='O') d1End=0; if(a[i][5-i]!=a[i-1][5-i+1]||a[i][5-i]=='O') d2End=0; } if(d1End||d2End) return 1; return 0; } void init() { for(int i=1;i<=4;++i) { for(int j=1;j<=4;++j) cin>>a[i][j]; } } void p() { for(int i=1;i<=4;++i) { for(int j=1;j<=4;++j) cout<<a[i][j]; cout<<endl; } } inline const int getId() const { int p=0,u=1; for(int i=1;i<=4;++i) for(int j=1;j<=4;++j) { if(a[i][j]=='B') p+=1*u; if(a[i][j]=='W') p+=2*u; u*=3; } return p; } inline char *at(const int& x,const int& y) { if(x<1||x>4||y<1||y>4) return NULL; return &a[x][y]; } }; int stepL; short stepD[50000000]={}; const bool dfs(state now,const int &step,bool color) { //now.p(); if(step>stepL) return 0; if(now.isEnd()) return 1; int nid=now.getId(); if(stepD[nid]&&stepD[nid]<step) return 0; stepD[nid]=step; for(int i=1;i<=4;++i) { for(int j=1;j<=4;++j) { for(int dir=0;dir<4;++dir) { int newi=i+deltaX[dir],newj=j+deltaY[dir]; if(now.at(newi,newj)==NULL) continue; if(*now.at(newi,newj)!='O'||*now.at(i,j)!=oC[color])//第一次写的时候没有看到要交替下棋 continue; swap(*now.at(newi,newj),*now.at(i,j)); if(dfs(now,step+1,!color)) return 1; swap(*now.at(newi,newj),*now.at(i,j)); } } } return 0; } state c; int main() { c.init(); for(stepL=1;stepL<=100;++stepL) { if(dfs(c,1,0)||dfs(c,1,1)){ printf("%d",stepL-1); return 0; } } }