首页 > ACM题库 > 九度OJ > 九度-1091-棋盘游戏[解题代码]
2013
12-12

九度-1091-棋盘游戏[解题代码]

题目来源:2005年上海交通大学计算机研究生机试真题

题目描述:

    有一个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

cpp 代码如下:
#include <iostream>
#include <queue>
using namespace std;

class Node
{
public:
	int x, y, sum, statu;
};

int ans;
int map[6][6];
int opt[6][6][5]; //记录最优解,剪枝条件
Node start;
int ex, ey;
int cnt = 0;
int dir[4][2] =
{
{ 0, 1 },
{ 1, 0 },
{ 0, -1 },
{ -1, 0 } };
queue<Node> q;
void bfs(Node n)
{
	q.push(n);
	int tempx, tempy, cost;
	while (!q.empty())
	{
		cnt++;
		Node tn = q.front();
		q.pop();
		//opt[tn.x][tn.y] = tn.sum ;
		for (int i = 0; i < 4; i++)
		{
			tempx = tn.x + dir[i][0];
			tempy = tn.y + dir[i][1];
			if (tempx >= 0 && tempx < 6 && tempy >= 0 && tempy < 6)
			{
				cost = tn.statu * map[tempx][tempy];
				if (tn.sum + cost < opt[tempx][tempy][cost % 4 ]
						&& tn.sum + cost < opt[ex][ey][cost % 4 ])
				{
					opt[tempx][tempy][cost % 4] = tn.sum + cost;
					Node temp;
					temp.x = tempx;
					temp.y = tempy;
					temp.sum = tn.sum + cost;
					temp.statu = cost % 4 + 1;
					q.push(temp);
				}
			}
		}
	}

}

int main()
{
	int k;
	cin >> k;
	while (k--)
	{
		for (int i = 0; i < 6; i++)
			for (int j = 0; j < 6; j++)
			{
				cin >> map[i][j];
				for(int k=0; k<4; k++)
					opt[i][j][k] = 100000;
			}
		start.sum = 0;
		start.statu = 1;
		ans = 100000;

		cin >> start.x >> start.y >> ex >> ey;
		bfs(start);
		for (int i = 0; i < 4; i++)
		{
			if (ans > opt[ex][ey][i])
				ans = opt[ex][ey][i];
		}
		cout << ans << endl;
	}
	return 0;
}
/**************************************************************
	Problem: 1091
	User: coder
	Language: C++
	Result: Accepted
	Time:0 ms
	Memory:1520 kb
****************************************************************/


  1. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  2. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢