每日一九度之 题目1091：棋盘游戏
九度又可以刷题啦~~
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：1859
解决：517
有一个6*6的棋盘，每个棋盘上都有一个数值，现在又一个起始位置和终止位置，请找出一个从起始位置到终止位置代价最小的路径：
1、只能沿上下左右四个方向移动
2、总代价是没走一步的代价之和
3、每步（从a,b到c,d）的代价是c,d上的值与其在a,b上的状态的乘积
4、初始状态为1
每走一步，状态按如下公式变化：（走这步的代价%4）+1。
</dd> </dl> <dl> <dt> 输入： </dt> <dd> 第一行有一个正整数n，表示有n组数据。
每组数据一开始为6*6的矩阵，矩阵的值为大于等于1小于等于10的值，然后四个整数表示起始坐标和终止坐标。
输出最小代价。
</dd> </dl> <dl> <dt> 样例输入： </dt> <dd>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</dd> </dl> <dl> <dt> 样例输出： </dt> <dd>
23</dd> </dl>
简单回溯，但是要注意状态的变化。
//Asimple #include <bits/stdc++.h> #define INF 0xfffffff #define mod 10007 #define swap(a,b,t) t = a, a = b, b = t #define CLS(a, v) memset(a, v, sizeof(a)) #define debug(a) cout << #a << " = " << a <<endl #define abs(x) x<0?-x:x #define srd(a) scanf("%d", &a) #define src(a) scanf("%c", &a) #define srs(a) scanf("%s", a) #define srdd(a,b) scanf("%d %d",&a, &b) #define srddd(a,b,c) scanf("%d %d %d",&a, &b, &c) #define prd(a) printf("%d\n", a) #define prdd(a,b) printf("%d %d\n",a, b) #define prs(a) printf("%s\n", a) #define prc(a) printf("%c", a) using namespace std; typedef long long ll; const int maxn = 6; int dx[] = {-1,1,0,0}, dy[]={0,0,-1,1}; int n, m, num, T, k, len, ans, sum; int edx, edy, stx, sty; int Map[maxn][maxn]; bool vis[maxn][maxn]; bool wrong(int x, int y) { return x<0 || x>=maxn || y<0 || y>=maxn || vis[x][y]; } void output() { prd(ans); } void solve(int x, int y, int step, int v) { if( ans > step ) { if( x == edx && y == edy ) { ans = step; return ; } else { for(int i=0; i<4; i++) { int xx = x + dx[i]; int yy = y + dy[i]; if( !wrong(xx, yy) ) { int cost = v * Map[xx][yy]; int st = step+cost; int va = cost%4 + 1; vis[xx][yy] = true; solve(xx, yy, st, va); vis[xx][yy] = false; } } } } } void input() { srd(n); while( n -- ) { CLS(vis, false); for(int i=0; i<maxn; i++) { for(int j=0; j<maxn; j++) { srd(Map[i][j]); } } srdd(stx, sty); srdd(edx, edy); ans = INF; solve(stx, sty, 0, 1); output(); } } int main(){ input(); return 0; }
华为成长空间 479人发布
查看5道真题和解析
