sicily1702 Robot Roll Call -- Cambot...Servo...Gypsy...Croooow
IAmL
posted @ 2009年4月20日 07:30
in 解题报告
with tags
sicily1702解题报告
, 3048 阅读
这题是周赛题，当时我的想法是回溯，当然是超时，但是我还是试了，真是sb。之后就是想到把原来的图换成另外一个图。具体做法是首先把点从1～n^2编号，点（i，j）的编号为i*j。然后由于点（i， j）和它上下左右的点相连，所以i*j就和（i-1）*j，（i+1）*j，i*（j-1），i*（j+1）相连，他们的权值就是（i，j）的权值。之后用dijkstra求出最短路，再加上点（n-1，n-1）的权值就可以了。虽然说这个方法可行，但是很麻烦，超时的可能性很大，而且但是心情不好，所以我当时就没有试，后来在bbs上看到了和我思路差不多的算法，才验证了这个思路的可行性。
但是之后发现了一个更厉害的算法，就是BFS，但是该算法的提出者称之为：激情小广搜。呵呵。主要思路就是：用f[i][j]记录到（i，j）的最短路径，然后对（i，j）进行扩展的条件是找到从某个点到（i，j）这一点的新的最短路小于原来的f[i][j]。这个思路和我之前做过的广搜的不同之处就是加入了剪枝，而且不是不是纯粹的对状态进行搜索，而是对最优解答案进行搜索。从个人感觉上，有点像dp……
＝＝＝＝＝＝＝不明真相的分割线＝＝＝＝＝＝＝＝＝＝
#pragma warning(disable:4786)
#include <iostream>
#include <queue>
using namespace std;
#define N 130
int m[N][N], f[N][N], n;
const int move[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
struct point
{
int x, y;
}p;
void BFS()
{
queue<point> q;
int x, y, k, tmp;
for (x = 0; x < n; x++)
for (y = 0; y < n; y++)
f[x][y] = 2500;
p.x = 0;
p.y = 0;
f[0][0] = m[0][0];
q.push(p);
while (!q.empty())
{
p = q.front();
q.pop();
x = p.x;
y = p.y;
for (k = 0; k < 4; k++)
{
p.x += move[k][0];
p.y += move[k][1];
if (p.x >= 0 && p.x < n && p.y >= 0 && p.y < n)
{
tmp = f[x][y] + m[p.x][p.y];
if (f[p.x][p.y] > tmp)
{
f[p.x][p.y] = tmp;
q.push(p);
}
}
p.x = x;
p.y = y;
}
}
}
int main()
{
int i, j, tn = 0;
while (cin >> n, n)
{
tn++;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
cin >> m[i][j];
BFS();
cout << "Problem " << tn << ": " << f[n - 1][n - 1] << endl;
}
return 0;
}
#include <iostream>
#include <queue>
using namespace std;
#define N 130
int m[N][N], f[N][N], n;
const int move[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
struct point
{
int x, y;
}p;
void BFS()
{
queue<point> q;
int x, y, k, tmp;
for (x = 0; x < n; x++)
for (y = 0; y < n; y++)
f[x][y] = 2500;
p.x = 0;
p.y = 0;
f[0][0] = m[0][0];
q.push(p);
while (!q.empty())
{
p = q.front();
q.pop();
x = p.x;
y = p.y;
for (k = 0; k < 4; k++)
{
p.x += move[k][0];
p.y += move[k][1];
if (p.x >= 0 && p.x < n && p.y >= 0 && p.y < n)
{
tmp = f[x][y] + m[p.x][p.y];
if (f[p.x][p.y] > tmp)
{
f[p.x][p.y] = tmp;
q.push(p);
}
}
p.x = x;
p.y = y;
}
}
}
int main()
{
int i, j, tn = 0;
while (cin >> n, n)
{
tn++;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
cin >> m[i][j];
BFS();
cout << "Problem " << tn << ": " << f[n - 1][n - 1] << endl;
}
return 0;
}
评论 (0)