九度OJ 1091:棋盘游戏 (DP、BFS、DFS、剪枝)
2024-09-07 19:02:53
时间限制:1 秒
内存限制:32 兆
特殊判题:否
提交:1497
解决:406
- 题目描述:
-
有一个6*6的棋盘,每个棋盘上都有一个数值,现在又一个起始位置和终止位置,请找出一个从起始位置到终止位置代价最小的路径:
1、只能沿上下左右四个方向移动
2、总代价是没走一步的代价之和
3、每步(从a,b到c,d)的代价是c,d上的值与其在a,b上的状态的乘积
4、初始状态为1每走一步,状态按如下公式变化:(走这步的代价%4)+1。
- 输入:
-
第一行有一个正整数n,表示有n组数据。
每组数据一开始为6*6的矩阵,矩阵的值为大于等于1小于等于10的值,然后四个整数表示起始坐标和终止坐标。
- 输出:
-
输出最小代价。
- 样例输入:
-
1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
0 0 5 5
- 样例输出:
-
23
思路:
本题我开始不会做,参考了别人的博客做出来的。
此题比较好的办法是用BFS,求的过程中要适当剪枝。
DFS也可求解。
参考的博客地址:
http://blog.csdn.net/gladyoucame/article/details/8803904
里面分别用C++实现了BFS和DFS。
我的C代码:
#include <stdio.h>
#include <stdlib.h>
#define INF (1e9)
#define M (6*6*4+1)
typedef struct node {
int x, y;
int sum;
int state;
} Point;
int cost[6][6][4];
int value[6][6];
Point begin, end;
int dir[4][2] = {{0, 1},{1, 0},{0, -1},{-1, 0}};
Point *queue[M];
int front, rear;
void initQueue()
{
front = rear = 0;
}
int isEmpty()
{
return front == rear;
}
void push(Point *a)
{
queue[rear] = a;
rear = (rear+1)%M;
}
Point *top()
{
return queue[front];
}
void pop()
{
front = (front+1)%M;
}
void BFS()
{
int i;
push(&begin);
while (!isEmpty())
{
Point *p = top();
pop();
for (i=0; i<4; i++)
{
int tx = p->x + dir[i][0];
int ty = p->y + dir[i][1];
if (tx>=0 && tx<6 && ty>=0 && ty<6)
{
int tcost = p->state * value[tx][ty];
int costNow = p->sum + tcost;
if (costNow < cost[tx][ty][tcost%4]
&& costNow < cost[end.x][end.y][tcost%4])
{
cost[tx][ty][tcost%4] = costNow;
Point *p1 = (Point *)malloc(sizeof(Point));
p1->x = tx;
p1->y = ty;
p1->sum = costNow;
p1->state = tcost%4 + 1;
push(p1);
}
}
}
if (p != &begin)
free(p);
}
}
int Min(int a, int b)
{
return (a<b) ? a : b;
}
int main(void)
{
int n, i, j, k;
scanf("%d", &n);
while (n--)
{
for (i=0; i<6; i++)
{
for (j=0; j<6; j++)
{
scanf("%d", &value[i][j]);
for (k=0; k<4; k++)
cost[i][j][k] = INF;
}
}
scanf("%d%d", &begin.x, &begin.y);
scanf("%d%d", &end.x, &end.y);
begin.sum = 0;
begin.state = 1;
initQueue();
BFS();
int min = INF;
for(i=0; i<4; i++)
min = Min(cost[end.x][end.y][i], min);
printf("%d\n", min);
}
return 0;
}
/**************************************************************
Problem: 1091
User: liangrx06
Language: C
Result: Accepted
Time:0 ms
Memory:916 kb
****************************************************************/
最新文章
- 关于跨域GET、POST请求的小结//////////////////////zzzzzzz
- CentOS配置SVN服务器
- java 调用 r, Can&#39;t find dependent libraries
- php 函数ignore_user_abort()
- Sqli-labs less 41
- POJ1986 DistanceQueries 最近公共祖先LCA 离线算法Tarjan
- PHP webserver 之 soap wsdl
- Hibernate中的一对多关系详解(2)
- 树莓派学习路程No.1 GPIO功能初识 wiringPi安装
- 编写Swift代码的其他工具
- CSS3秘笈:第五章
- UIscrollView 代理
- hdu_1711: Number Sequence【KMP算法】
- CKEdit( htm编辑器)
- 遇到502错误,invalid request block size 解决方法
- zookeeper.KeeperException$UnimplementedException: KeeperErrorCode = Unimplemented for {root.path}
- java函数式编程之Supplier
- Hadoopif.for.while 语句
- Cloudstack安装(二)
- python脚本 pyqt 打包成windows可执行exe文件 pyinstaller
热门文章
- WEB学习-兼容问题
- js -“=”“==”和“===”的区别
- Codeforces Gym101502 K.Malek and Summer Semester
- RichEditControl(富文本控件)
- Linux VFS
- CF768
- 51NOD 1833 环
- codeforces 979E(dp套dp)
- JVM 常用命令
- xamarin android 获取根证书代码