【CodeVS 1004】四子连棋
2024-08-28 17:26:25
http://blog.csdn.net/u013598409/article/details/43924465
相比于一年半前,代码的掌控能力强了许多。
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define per(i,a,b) for (int i=(a);i>=(b);i--)
const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
char s[4][4];
int dep;
map<int,int> mp;
inline int cid(char c)
{
if (c=='W') return 0;
else if (c=='B') return 1;
else if (c=='O') return 2;
}
inline int ST(void)
{
int sum=0;
rep(i,0,3)
rep(j,0,3)
sum=sum*3+cid(s[i][j]);
return sum;
}
inline int Check(void)
{
char t;
rep(i,0,3)
{
t=s[i][0];
if (t==s[i][1]&&t==s[i][2]&&t==s[i][3]) return 1;
}
rep(i,0,3)
{
t=s[0][i];
if (t==s[1][i]&&t==s[2][i]&&t==s[3][i]) return 1;
}
t=s[0][0];
if (t==s[1][1]&&t==s[2][2]&&t==s[3][3]) return 1;
t=s[3][0];
if (t==s[2][1]&&t==s[1][2]&&t==s[0][3]) return 1;
return 0;
}
inline int Legal(int x,int y)
{
return 0<=x&&x<=3&&0<=y&&y<=3;
}
int DFS(int dir,int tms,int lim)
{
int st=ST();
if (mp.count(st)) return 0;
mp[st]=1;
if (tms==lim)
{
int t=Check();
return t;
}
rep(x,0,3) rep(y,0,3) if (cid(s[x][y])==dir)
rep(k,0,3)
{
int nx=x+dx[k],ny=y+dy[k];
if (Legal(nx,ny)&&cid(s[nx][ny])==2)
{
swap(s[x][y],s[nx][ny]);
int t=DFS(dir^1,tms+1,lim);
swap(s[x][y],s[nx][ny]);
if (t) return 1;
}
}
return 0;
}
int main(void)
{
// freopen("codevs1004.in","r",stdin);
// freopen("codevs1004.out","w",stdout);
rep(i,0,3)
scanf("%s",s[i]);
int t1,t2; dep=-1;
do
{
dep++;
mp.clear();
t1=DFS(0,0,dep);
mp.clear();
t2=DFS(1,0,dep);
}while (!t1&&!t2);
printf("%d\n",dep);
return 0;
}
最新文章
- windows 7(32/64位)GHO安装指南(U盘制作篇)~
- oracle课堂笔记
- LNMP环境简易安装流程
- PL/SQL工具连接ORALCE数据库的方法
- c#关于委托和事件(二)(介绍的很详细)
- 【译文】漫谈ASP.NET中的Session
- StringBuilder和StringBuffer
- 【3D研发笔记】之【数学相关】(一):坐标系
- 手机端的mousedown
- Delphi过程函数传递参数的八种方式
- Python &; virtualenv使用说明
- es6第一章 continue
- 不使用 webpack,vuejs 异步加载模板
- CentOS 6.4 源码安装MySQL 5.6
- java菜鸟之微信分享
- Socket接口
- liunx基础命令
- 001_fpm打包命令详解
- std::max 错误
- 【BZOJ】1684: [Usaco2005 Oct]Close Encounter(暴力+c++)
热门文章
- linux ssh 使用深度解析(key登录详解)
- VC++ 线程同步 总结
- BZOJ 1822 Frozen Nova 冷冻波(最大流)
- 一个js搜索功能的实现
- UVA 1424	 二 Salesmen
- PCB表面处理工艺
- Beaglebone Black&ndash; 智能家居控制系统 LAS - 网页服务器 Node.js 、Web Service、页面 和 TCP 请求转 UDP 发送
- ASP.NET四则运算--策略模式
- hdu 2196 Computer 树的直径
- XAF应用开发教程(二)业务对象模型之简单类型属性