一、题目

  Kind of a Blur

二、分析

  题目读起来挺费劲的。

  主要就是要求一个矩阵,其中每个点及其于这个的曼哈顿距离小于D的点的值总和的平均值就是新生成的矩阵。

  给定新生成的矩阵,求初始矩阵。

  相当于就是一个点的值与多个点的值相关联,那么列一个(WH)列,(WH)个未知数的方程组,然后解方程就可以了,由于值是浮点型,那么就是浮点型的高斯消元。

三、AC代码

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define Min(a,b) ((a)>(b)?(b):(a))
#define Max(a,b) ((a)>(b)?(a):(b)) const int maxn = 2e2 + 20;
const double eps = 1e-7;
int W, H, D;
double M[20][20]; class GaussMatrix
{
public:
double a[maxn][maxn];
int equ, val; //行数、列数
void swapRow(int rowOne, int rowTwo)
{
for(int i = 1; i <= val; ++i)
{
swap(a[rowOne][i], a[rowTwo][i]);
}
}
void swapCol(int colOne, int colTwo)
{
for(int i = 1; i <= equ; ++i)
{
swap(a[i][colOne], a[i][colTwo]);
}
}
bool same(double x, double y)
{
return fabs(x - y) < eps;
}
int guass()
{
int k, col;
for(k = 1, col = 1; k <= equ && col < val; k++, col++)
{
//找到[k, equ]行中,col列值最大的行
int maxRow = k;
for(int i = k + 1; i <= equ; i++)
{
if(fabs(a[i][col]) > fabs(a[maxRow][col]))
{
maxRow = i;
}
}
//如果col列都为0,直接处理下一列
if(same(a[maxRow][col], 0))
{
--k;
continue;
}
if(maxRow != k)
swapRow(k, maxRow);
//约掉最上面这行约数,是当前行第col列第一个数系数为1
for(int i = col + 1; i <= val; i++)
{
a[k][i] /= a[k][col];
}
a[k][col] = 1.0;
//消元
//1*x + b*y + c*z = d1
//a2*x + b2*y + c2*z = d2
//a3*x + b3*y + c3*z = d3
for(int i = 1; i <= equ; i++)
{
if(i == k)
continue;
for(int j = col + 1; j <= val; j++)
{
a[i][j] -= a[i][col]*a[k][j];
}
a[i][col] = 0.0;
}
}
//扫描一下剩下的行,如果有解,则应全部都被消为了0
for(k; k <= equ; k++)
{
if(!same(a[k][val], 0))
return -1;
}
return val - k;
}
}arr; struct node
{
int x, y, len;
node(int a, int b, int l)
{
x = a, y = b;
len = l;
}
};
bool visited[20][20];
const int dx[] = {0, -1, 0, 1};
const int dy[] = {1, 0, -1, 0}; int toHash(int i, int j)
{
return (i-1)*W + j;
} bool judge(int x, int y)
{
if( !visited[x][y] && x > 0 && x <= H && y > 0 && y <= W)
return true;
return false;
} void init(int x, int y, int row)
{
memset(visited, 0, sizeof(visited));
queue<node> que;
memset(visited, 0, sizeof(visited));
que.push(node(x, y, 0));
int has = 0;
while(!que.empty())
{
node t = que.front();
que.pop();
if(t.len <= D && judge(t.x, t.y))
{
arr.a[row][toHash(t.x, t.y)] = 1.0;
has++;
for(int i = 0; i < 4; i++)
{
que.push(node(t.x+dx[i], t.y+dy[i], t.len+1));
}
}
visited[t.x][t.y] = 1;
}
arr.a[row][W*H+1] = M[x][y]*has;
} void solve()
{
int cnt = 0;
arr.equ = W*H;
arr.val = W*H + 1;
memset(arr.a, 0, sizeof(arr.a));
for(int i = 1; i <= H; i++)
{
for(int j = 1; j <= W; j++)
{
init(i, j, ++cnt);
}
}
arr.guass();
int to = 1;
for(int i = 1; i <= H; i++)
{
for(int j = 1; j <= W; j++)
{
printf("%8.2lf", arr.a[to++][W*H+1]);
}
printf("\n");
}
} int main()
{
//freopen("input.txt", "r", stdin);
bool flag = 0;
while(scanf("%d%d%d", &W, &H, &D) != EOF)
{
if( !(W+H+D) )
break;
if(flag)
puts("");
else
flag = 1;
for(int i = 1; i <= H; i++)
{
for(int j = 1; j <= W; j++)
{
scanf("%lf", &M[i][j]);
}
}
solve();
}
return 0;
}

最新文章

  1. intellij中不能导入jar包
  2. Javascript中,document.getElementsByName获取的就一定是数组了么?
  3. 使用vs2008搭建php扩展环境
  4. Ninject之旅之十:Ninject自定义提供者
  5. datePiker弹出框被其他div遮挡
  6. Codeforces Round #362 (Div. 2)-&gt;A. Pineapple Incident
  7. iOS 简单总结:description方法\NSLog函数
  8. Android的Bitmap和BitmapDrawable类解析-android学习之旅(六十)
  9. getopt()函数
  10. HDU - 5455 Fang Fang
  11. MySQL--当查询遇到隐藏字符
  12. JAVA设计模式---单例模式的几种实现方式比较
  13. 【CloverETL培训】题目
  14. 树莓派B+使用入门&amp;RPI库安装&amp;wringPi库安装
  15. Python里的赋值 拷贝 深拷贝
  16. requests库入门02-简单了解HTTP协议
  17. poj 3694 Network 【Tarjan】+【LCA】
  18. (常用)re模块
  19. wpf 控件大小随窗体大小改变而改变
  20. poj3436 ACM Computer Factory, 最大流,输出路径

热门文章

  1. 进程控制——fork-and-exec、system、wait
  2. mybatis(四)缓存机制
  3. 卧槽,sql注入竟然把我们的系统搞挂了
  4. Windows中VS code无法查看C++ STL容器的值 - 解决方法
  5. how to measure function performance in javascript
  6. HTML5 Learning Paths
  7. DoH &amp; DNS over HTTPS
  8. 星空值、SPC、算力组成三元永动机制!VAST带你把握时代!
  9. NGK算力持有好处多多!SPC、VAST等免费拿!
  10. 若依管理系统RuoYi-Vue(二):权限系统设计详解