文章目录
- 题意
-
- 样例
- 分析
-
- 参考题解1
- 参考题解2
- 参考题解3
题意
芯片二维平面图是一个n*n二维矩阵(0<n<300)，其中： 0表示core -1表示路径不通 其他正数表示电阻 路径电阻计算是路径上最大的电阻值。
| - | - | - | - |
|---|---|---|---|
| 14 | |||
| -1 | |||
| 7 | -1 | -1 | |
| 3 |
上面4*4矩阵中的加粗数，4个core(0)连接。路径电阻为4。
0<n<300 core数量小于100，大于0
样例
输入： 3 （n=3） 0 1 3 -1 2 1 0 1 1 输出： 2
分析
算出每个core到core0电阻，取最大值，即可。
题解1： 自归函数，自上而下
题解2： 递归函数，自底向上，9万次调用，栈溢出
非典型的DAG图，DP方法，刷表从头到尾都做不到。 因此，将更新的节点存储在队列中，刷新受影响的节点，直到收敛。 题解3： DP自底向上刷表
参考题解1
#include<stdio.h> #define MIN(a,b) (a)<(b)?(a):(b) #define MAX(a,b) (a)>(b)?(a):(b) int N, coreNum; ///矩阵范围N，核心数coreNum int chip[300][300]; int core[100][2]; //记录核心坐标 int dir[4][2] = {
{
1,0},{
0,1},{
-1,0},{
0,-1} };
//坐标xy到核心0的路径电阻。4代表从哪个方向递推来的
//因为有时候visit标记导致某个方向continue了
//所以必须要4个方向都递推过，坐标xy的路径电阻才能确认，然后才能使用memo
int memo[300][300][4] = {
0};
bool visit[300][300] = {
0 };
void input();
bool illeagle(int x, int y)
{
if (x < 0 || y < 0)
return false;
if(x > N-1 || y > N - 1)
return false;
if (chip[x][y] == -1)
return false;
return true;
}
int dfs(int x, int y) //坐标xy到核心0的最小路径电阻
{
int i, nextx, nexty;
int tmp = INT_MAX;
if (core[0][0] == x && core[0][1] == y)
return 0;
if (memo[x][y][0] != 0 &&
memo[x][y][1] != 0 &&
memo[x][y][2] != 0 &&
memo[x][y][3] != 0)
{
//4个中最小的
return MIN(MIN(MIN(memo[x][y][0], memo[x][y][1]), memo[x][y][2]), memo[x][y][3]);
}
for (i = 0; i < 4; i++)
{
nextx = x + dir[i][0];
nexty = y + dir[i][1];
if (memo[nextx][nexty][i] != 0)
{
tmp = MIN(tmp, memo[nextx][nexty][i]);
continue;
}
if (false==illeagle(nextx, nexty))
{
memo[nextx][nexty][i] = INT_MAX;
continue;
}
if (visit[nextx][nexty] == true)
continue;
visit[nextx][nexty] = true;
memo[nextx][nexty][i] = dfs(nextx, nexty);
visit[nextx][nexty] = false;
tmp = MIN(tmp, dfs(nextx, nexty));
}
return MAX(tmp, chip[x][y]);
}
/* 3 0 1 3 -1 2 1 0 1 1 5 0 1 1 3 2 -1 -1 2 0 6 -1 -1 5 1 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 */
int main()
{
int i, j;
int res = 0;
input();
for (i = 1; i < coreNum; i++) //计算每个core到0号core的电阻，取最大值
{
visit[core[i][0]][core[i][1]] = true;
res = MAX(res, dfs(core[i][0], core[i][1]));
visit[core[i][0]][core[i][1]] = false;
}
}
void input()
{
int i = 0; int j = 0;
coreNum = 0;
scanf("%d", &N);
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
{
scanf("%d", &chip[i][j]);
if (chip[i][j] == 0)
{
core[coreNum][0] = i;
core[coreNum][1] = j;
coreNum++;
}
}
}
}
参考题解2
#include<stdio.h>
#define MIN(a,b) (a)<(b)?(a):(b)
#define MAX(a,b) (a)>(b)?(a):(b)
int N, coreNum; //矩阵范围N，核心数coreNum
int chip[300][300];
int core[100][2]; //记录核心的坐标
int dir[4][2] = {
{
1,0},{
0,1},{
-1,0},{
0,-1} };
int memo[300][300] = {
0};
void input();
bool illeagle(int x, int y)
{
if (x < 0 || y < 0)
return false;
if(x > N-1 || y > N - 1)
return false;
if (chip[x][y] == -1)
return false;
return true;
}
void updated(int x, int y)
{
int i = 0;
int nextx, nexty;
int memonext;
for (i=0;i<4;i++) //xy更新了，遍历xy四周的4个点尝试被更新
{
nextx = x + dir[i][0];
nexty = y + dir[i][1];
if (true==illeagle(nextx, nexty))
{
//nextxy 到core0的路径值比xy大，可以更新一下。
//更新为chip[nextx][nexty]或者memo[x][y]。
memonext = MAX(MIN(memo[nextx][nexty], memo[x][y]), chip[nextx][nexty]);
if (memonext!= memo[nextx][nexty])
{
memo[nextx][nexty] = memonext;
updated(nextx, nexty);//nextx真的更新了，就要更新nextx周围的点
}
}
}
}
/* 3 0 1 3 -1 2 1 0 1 1 5 0 1 1 3 2 -1 -1 2 0 6 -1 -1 5 1 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 */
int main()
{
int i, j;
int res = 0;
input();
memo[core[0][0]][core[0][1]] = 0;
updated(core[0][0], core[0][1]); //0号core的坐标开始更新，影响4周的4个点
}
void input()
{
int i = 0; int j = 0;
coreNum = 0;
scanf("%d", &N);
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
{
scanf("%d", &chip[i][j]);
if (chip[i][j] == 0)
{
core[coreNum][0] = i;
core[coreNum][1] = j;
coreNum++;
}
memo[i][j] = INT_MAX;
}
}
}
参考题解3
#include<stdio.h>
#define MIN(a,b) (a)<(b)?(a):(b)
#define MAX(a,b) (a)>(b)?(a):(b)
int N, coreNum; //矩阵范围N，核心数coreNum
int chip[300][300];
int core[100][2]; //记录核心的坐标
int dir[4][2] = {
{
1,0},{
0,1},{
-1,0},{
0,-1} };
int memo[300][300] = {
0};
#define quelen (300*300)
int queue[quelen] = {
0};
bool inqueue[300][300] = {
0 };
void input();
bool illeagle(int x, int y)
{
if (x < 0 || y < 0)
return false;
if(x > N-1 || y > N - 1)
return false;
if (chip[x][y] == -1)
return false;
return true;
}
/* 3 0 1 3 -1 2 1 0 1 1 5 0 1 1 3 2 -1 -1 2 0 6 -1 -1 5 1 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 10 12 5 7 3 4 13 1 5 10 17 13 19 18 5 2 9 11 7 15 15 11 16 20 12 8 4 1 9 16 13 7 5 14 12 16 0 11 10 16 19 2 1 11 4 19 7 12 12 1 9 10 3 15 0 14 19 4 18 12 14 20 6 7 9 3 12 4 11 15 20 1 1 6 6 2 14 6 7 4 17 16 13 12 4 13 4 5 3 19 13 6 12 3 5 0 12 0 10 20 17 */
int main()
{
int i, j;
int head = 0;
int tail = 0;
int x, y;
int nextx, nexty, memonext;
int tmp;
input();
memo[core[0][0]][core[0][1]] = 0;
//从core0开始，core0坐标放入队列
queue[tail++] = core[0][0] * N + core[0][1];
inqueue[core[0][0]][core[0][1]] = true;
while (tail!=head) //队列非空，有memo更新了，尝试更新周围的点
{
tmp = queue[head++]; //取出一个点
head = head % quelen;
x = tmp / N;
y = tmp % N;
inqueue[x][y] = false;
for (i = 0; i < 4; i++) //更新这个点四周的点
{
nextx = x + dir[i][0];
nexty = y + dir[i][1];
if (true == illeagle(nextx, nexty))
{
memonext = MAX(MIN(memo[nextx][nexty], memo[x][y]), chip[nextx][nexty]);
if (memonext != memo[nextx][nexty])
{
memo[nextx][nexty] = memonext;
//nextx更新了，把它放到队列
if (inqueue[nextx][nexty] == false)
{
queue[tail++] = nextx * N + nexty;
tail = tail % quelen;
inqueue[nextx][nexty] = true;
}
}
}
}
}
}
void input()
{
int i = 0; int j = 0;
coreNum = 0;
scanf("%d", &N);
//N = 299;
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
{
//chip[i][j] = rand() % 10;
//if (chip[i][j] > 8 || (chip[i][j]==0 && coreNum==100))
// chip[i][j] = -1;
scanf(