CODEVS 1004四子连棋
2024-10-21 01:40:34
【题目描述 Description】
在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。
| ● | ○ | ● | |
| ○ | ● | ○ | ● |
| ● | ○ | ● | ○ |
| ○ | ● | ○ |
输入描述 Input Description
从文件中读入一个4*4的初始棋局，黑棋子用B表示，白棋子用W表示，空格地带用O表示。
输出描述 Output Description
用最少的步数移动到目标棋局的步数。
样例输入 Sample Input
BWBO
WBWB
BWBW
WBWO
样例输出 Sample Output
5
【解题思路】
只能这样说，这是一个特别练DFS和BFS的题目，因为它的数据范围很小，怎么搜都不会超时，但是写深搜的孩子要注意，不能只从一个空格开始搜，而是在搜索完每一个节点之后都要进行一个双重循环寻找空格，因为空格有两个！有两个！
program FourChess;
const fx:array[..] of longint=(,-,,);
fy:array[..] of longint=(,,,-);
var
f:array[..,..] of longint;
i,j:longint;
min:longint;
ch:char; procedure dfs(x,y,num,co:longint);
var i,j,k,m,flag:longint;
begin
flag:=;
if num>=min then exit;
for i:= to do
begin
if (f[i,]=f[i,]) and(f[i,]=f[i,]) and(f[i,]=f[i,])and((f[i,]=) or(f[i,]=)) then
BEGIN
m:=num;
flag:=;
end;
if (f[,i]=f[,i]) and(f[,i]=f[,i]) and(f[,i]=f[,i]) and((f[,i]=) or(f[,i]=))then
begin
m:=num;
flag:=;
end;
end;
if (f[,]=f[,]) and(f[,]=f[,]) and (f[,]=f[,]) and((f[,]=) or(f[,]=))then
begin
m:=num;
flag:=;
end;
if (f[,]=f[,]) and(f[,]=f[,]) and(f[,]=f[,]) and((f[,]=) or(f[,]=))then
begin
m:=num;
flag:=;
end;
if (m<min) and (flag=) then
begin
min:=m;
exit;
end; for k:= to do
if (x+fx[k]>) and(x+fx[k]<) and (y+fy[k]>) and(y+fy[k]<) and (f[x+fx[k],y+fy[k]]=co) then
begin f[x,y]:=f[x+fx[k],y+fy[k]];
f[x+fx[k],y+fy[k]]:=;
if co= then co:= else co:=;
for i:= to do
for j:= to do
if f[i,j]= then
dfs(i,j,num+,co);
if co= then co:= else co:=; f[x+fx[k],y+fy[k]]:=F[X,Y];
f[x,y]:=;
end; end; begin
min:=maxlongint;
for i:= to do
begin
for j:= to do
begin
read(ch);
if ch='W' then f[i,j]:=;
if ch='B' then f[i,j]:=;
end;
readln;
end;
for i:= to do
for j:= to do
if f[i,j]= then
begin
dfs(i,j,,);
dfs(i,j,,);
end;
writeln(min);
end.
DFS
program FourChess;
const fx:array[..] of longint=(,-,,);
fy:array[..] of longint=(,,,-);
var
f:array[..,..] of longint;
i,j:longint;
min:longint;
ch:char; procedure dfs(x,y,num,co:longint);
var i,j,k,m,flag:longint;
begin
flag:=;
if num>=min then exit;
for i:= to do
begin
if (f[i,]=f[i,]) and(f[i,]=f[i,]) and(f[i,]=f[i,])and((f[i,]=) or(f[i,]=)) then
BEGIN
m:=num;
flag:=;
end;
if (f[,i]=f[,i]) and(f[,i]=f[,i]) and(f[,i]=f[,i]) and((f[,i]=) or(f[,i]=))then
begin
m:=num;
flag:=;
end;
end;
if (f[,]=f[,]) and(f[,]=f[,]) and (f[,]=f[,]) and((f[,]=) or(f[,]=))then
begin
m:=num;
flag:=;
end;
if (f[,]=f[,]) and(f[,]=f[,]) and(f[,]=f[,]) and((f[,]=) or(f[,]=))then
begin
m:=num;
flag:=;
end;
if (m<min) and (flag=) then
begin
min:=m;
exit;
end; for k:= to do
if (x+fx[k]>) and(x+fx[k]<) and (y+fy[k]>) and(y+fy[k]<) and (f[x+fx[k],y+fy[k]]=co) then
begin f[x,y]:=f[x+fx[k],y+fy[k]];
f[x+fx[k],y+fy[k]]:=;
if co= then co:= else co:=;
for i:= to do
for j:= to do
if f[i,j]= then
dfs(i,j,num+,co);
if co= then co:= else co:=; f[x+fx[k],y+fy[k]]:=F[X,Y];
f[x,y]:=;
end; end; begin
min:=;
for i:= to do
begin
for j:= to do
begin
read(ch);
if ch='W' then f[i,j]:=;
if ch='B' then f[i,j]:=;
end;
readln;
end;
for i:= to do
for j:= to do
if f[i,j]= then
begin
dfs(i,j,,);
dfs(i,j,,);
end;
writeln(min);
end.
BFS
最新文章
- Bootstrap学习笔记博客
- 玩转SQL Server复制回路の变更数据类型、未分区表转为分区表
- git学习1：git安装和配置
- 嵌套div中margin-top转移问题的解决办法
- JAVA数据库连接池实现（转）
- GhostDoc：生成.NET API文档的工具 (帮忙文档)
- CALayer 的 position和anchorPoint属性
- 类似与三元表达式的 json 读取值
- python运维开发之第四天
- 测试Flask+PYTHON的WEB框架
- C++语言之构造函数
- sql 语句中count()有条件的时候为什么要加上or null
- HDU 2089 不要62【解题报告】
- .NET Core到底有多强?
- python 基本运算符
- 中国地图（Highmaps）
- .33-浅析webpack源码之doResolve事件流(5)
- 二维数组 cudaMallocPitch() 和三维数组 cudaMalloc3D() 的使用
- SVM (support vector machine)
- Hadoop基础-Hadoop快照管理