编程求m*n土地腐化问题,谁有好的算法?
发布网友
发布时间：2022-04-23 02:13
共2个回答
热心网友
时间：2023-09-22 02:28
main.cxx
-------------------------------------------------------------------
#include <iostream>
#include "corruption.hxx"
void mp_corruption(int infect_no, int corrupt_time, int corrupted, int infected,
const Corruption& c)
{
std::cout << "no: " << infect_no
<< ", time: " << corrupt_time
<< ", corrupted: " << corrupted
<< ", infected: " << infected << std::endl;
std::cout << c << std::endl;
}
int main(int argc, char** argv)
{
int column = 10;
int row = 10;
int corrupt = 77;
Corruption c(column, row, corrupt);
std::cout << "column: " << column << ", row: " << row
<< ", corrupt: " << corrupt << ", occasion: ("
<< c.getOccasionRow() << ", " << c.getOccasionColumn()
<< ")" << std::endl;
std::cout << c << std::endl;
int spent = c.corrupt(mp_corruption);
std::cout << "time spent: " << spent << std::endl;
return 0;
}
corruption.hxx
------------------------------------------------------------------
#ifndef CORRUPTION_HXX
#define CORRUPTION_HXX
#include <iostream>
#include <vector>
typedef struct
{
int row; // 节点所处行
int column; // 节点所处列
int corrupt; // 节点腐化所需时间
char status; // 节点状态（'+': 尚未腐化； '%': 正在腐化； '-': 完全腐化）
char reserve[3]; // 保留
} Node;
class Corruption;
// 每次传染发生时，触发的回调函数（这里用来打日志）
typedef void (*infect_callback)(int infect_no, int corrupt_time, int corrupted, int infected,
const Corruption& c);
class Corruption
{
public:
Corruption();
Corruption(int row, int column, int corrupt);
virtual ~Corruption();
int getOccasionRow();
int getOccasionColumn();
int corrupt(infect_callback callback);
friend std::ostream& operator<< (std::ostream& os, const Corruption& c);
private:
int infect(int row, int column, std::vector<Node*>& corruping_list);
private:
int max_row; // 最大列数
int max_column; // 最大行数
int max_corrupt; // 最大*指数
int occasion_row; // 起因行
int occasion_column; // 起因列
Node **node_matrix; // 节点数组
};
#endif // CORRUPTION_HXX
corruption.cxx
------------------------------------------------------------------
#include "corruption.hxx"
#include <cstdlib>
#include <ctime>
#include <climits>
#include <vector>
Corruption::Corruption()
: max_row(0), max_column(0), max_corrupt(0)
{
this->node_matrix = NULL;
}
Corruption::Corruption(int row, int column, int corrupt)
: max_row(row), max_column(column), max_corrupt(corrupt)
{
// 用随机数初始化各节点
srand(time(NULL));
this->node_matrix = new Node*[this->max_row];
for (int i = 0; i < this->max_row; i++)
{
this->node_matrix[i] = new Node[this->max_column];
Node *p = this->node_matrix[i];
for (int j = 0; j < this->max_column; j++, p++)
{
double tmp = (double)rand();
tmp = tmp / RAND_MAX * this->max_corrupt + 1.0;
p->row = i;
p->column = j;
p->corrupt = (int)tmp;
p->status = '+';
}
}
this->occasion_row = (double)rand() / RAND_MAX * this->max_row;
this->occasion_column = (double)rand() / RAND_MAX * this->max_column;
}
Corruption::~Corruption()
{
// 释放资源
for (int i = 0; i < this->max_row; i++)
{
delete[] this->node_matrix[i];
this->node_matrix[i] = NULL;
}
delete[] this->node_matrix;
this->node_matrix = NULL;
}
// *起始行
int Corruption::getOccasionRow()
{
return this->occasion_row;
}
// *起始列
int Corruption::getOccasionColumn()
{
return this->occasion_column;
}
// 节点开始*
int Corruption::corrupt(infect_callback callback)
{
using namespace std;
vector<Node*> corrupting_list; // 正在腐化的节点
vector<Node*> corrupted_list; // 已经腐化的节点
Node *p = &(this->node_matrix[this->occasion_row][this->occasion_column]);
p->status = '%';
corrupting_list.push_back(p);
int infect_no = 1; // 传染次数
if (callback != NULL)
{
(*callback)(infect_no, 0, 0, 1, *this);
}
int corrupt_total = 0; // 总腐化时间
unsigned int count = this->max_column * this->max_row;
while (corrupted_list.size() < count)
{
infect_no++;
int corrupt_time = INT_MAX; // 本轮腐化时间
vector<Node*>::iterator it;
for (it = corrupting_list.begin(); it != corrupting_list.end(); it++)
{
p = (Node*)*it;
if (p->corrupt < corrupt_time)
{
corrupt_time = p->corrupt;
}
}
vector<Node*> tmp_list;
int corrupted = 0; // 本轮腐化节点数
int infected = 0; // 本轮传染节点数
for (it = corrupting_list.begin(); it != corrupting_list.end(); it++)
{
p = (Node*)*it;
p->corrupt -= corrupt_time;
if (p->corrupt <= 0)
{
p->status = '-';
corrupted++;
corrupted_list.push_back(p);
infected += this->infect(p->row, p->column, tmp_list);
}
else
{
tmp_list.push_back(p);
}
}
corrupting_list = tmp_list;
corrupt_total += corrupt_time;
if (callback != NULL)
{
(*callback)(infect_no, corrupt_time, corrupted, infected, *this);
}
}
return corrupt_total;
}
// 位于row行column的节点感染其附近的节点
int Corruption::infect(int row, int column, std::vector<Node*>& corrupting_list)
{
int count = 0; // 感染的节点数
Node *p = NULL;
if (row > 0)
{
if (column > 0)
{
p = &(this->node_matrix[row-1][column-1]);
if (p->status == '+')
{
p->status = '%';
corrupting_list.push_back(p);
count++;
}
}
p = &(this->node_matrix[row-1][column]);
if (p->status == '+')
{
p->status = '%';
corrupting_list.push_back(p);
count++;
}
if (column < this->max_column - 1)
{
p = &(this->node_matrix[row-1][column+1]);
if (p->status == '+')
{
p->status = '%';
corrupting_list.push_back(p);
count++;
}
}
}
if (column > 0)
{
p = &(this->node_matrix[row][column-1]);
if (p->status == '+')
{
p->status = '%';
corrupting_list.push_back(p);
count++;
}
}
if (column < this->max_column - 1)
{
p = &(this->node_matrix[row][column+1]);
if (p->status == '+')
{
p->status = '%';
corrupting_list.push_back(p);
count++;
}
}
if (row < this->max_row - 1)
{
if (column > 0)
{
p = &(this->node_matrix[row+1][column-1]);
if (p->status == '+')
{
p->status = '%';
corrupting_list.push_back(p);
count++;
}
}
p = &(this->node_matrix[row+1][column]);
if (p->status == '+')
{
p->status = '%';
corrupting_list.push_back(p);
count++;
}
if (column < this->max_column - 1)
{
p = &(this->node_matrix[row+1][column+1]);
if (p->status == '+')
{
p->status = '%';
corrupting_list.push_back(p);
count++;
}
}
}
return count;
}
std::ostream& operator<< (std::ostream& os, const Corruption& c)
{
os.fill('-');
os.width(c.max_column * 7);
os << "" << std::endl;
os.fill(' ');
os.width(0);
for (int i = 0; i < c.max_row; i++)
{
Node *p = c.node_matrix[i];
for (int j = 0; j < c.max_column; j++, p++)
{
os.width(4);
if (p->corrupt > 0)
{
os << p->corrupt << "(" << p->status << ")";
}
else
{
os << " " << "(" << p->status << ")";
}
}
os << std::endl;
}
return os;
}
热心网友
时间：2023-09-22 02:28
我看了下，就我来说一时半会弄不出来，然后去请教了一个牛人，给你一个代码外加测试数据
#include<iostream>
#include<queue>
#include<string>
using namespace std;
#define N 100
#define M 100
struct node
{
int x,y;
int time;
friend bool operator <(node a,node b)
{
return a.time>b.time;
}
};
node map[N][M];
bool mark[N][M];
int dia[N][M];
int x,y,n,m;
int dir[4][2]={1,0,0,1,-1,0,0,-1};//定义移动的方向
bool judge(int a,int b) //判断是否超界
{
if(a>=0&&a<n&&b>=0&&b<m)
return 1;
return 0;
}
int fun()
{
int i,q,p;
priority_queue<node> Q;
node now=map[x][y];
mark[x][y]=true;
now.time=dia[x][y];
Q.push(now);
while(!Q.empty())
{
now=Q.top();
Q.pop();
for(i=0;i<4;i++)
{
q=now.x+dir[i][0];
p=now.y+dir[i][1];
if(judge(q,p)&&mark[q][p]==false)
{
mark[q][p]=true;
map[q][p].time=now.time+dia[q][p];
Q.push(map[q][p]);
}
}
}
return now.time;
}
int main()
{
int i,j;
while(cin>>n>>m>>x>>y)
{
memset(mark,false,sizeof(mark));
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
cin>>dia[i][j];
map[i][j].x=i;
map[i][j].y=j;
}
cout<<fun()<<endl;
}
return 0;
}
大致的算法思想是优先队列，每次选出的是腐熟时间最短，然后它相邻的未腐化的变成腐化加入队列里面，中途记录最大值就行了或者是队列里面最底层的那个元素的完成时间。
测试数据：
3 3 0 0//n m x y
1 2 3
4 5 6
7 8 9
answer=21
