很巧啊。。去年就做了这么两道ACM,偏偏就选了这道。贴下我的代码吧。。。检查我是Hold不住了。。
#include
#include
using namespace std;
const int maxPairs=1000;
int inputpic[maxPairs][2]={0};//inputpic[][0]表示像素,inputpic[][1]表示起始位置
int outputpic[maxPairs*9][2]={0};
int inputNum=0;
int outputNum=0;
int WIDTH=0;
int TotalNum=0;
int endPos[2];
int getValue(int loc);
int cal(int loc);//计算Loc位置的最大值
int cal(int row, int col);//计算(row, col)位置的最大值
int getValue(int loc, int row, int col);//专门用来处理越界问题
int getInsertInd(int loc);
void insert(int temp[2]);//向outputpic中插入新的起始点
int main()
{
freopen("input.txt", "r", stdin);
while (1)
{
scanf("%d", &WIDTH);
if (WIDTH==0)
{
break;
}
int i=0, j=0, total=0;
while(scanf("%d %d", &inputpic[i][0], &j)!=EOF)
{
inputpic[i][1]=total;
total+=j;
if (j==0)
{
break;
}
i++;
}
inputNum = i;
TotalNum = total;
endPos[0] = total/WIDTH-1;
endPos[1] = WIDTH-1;
outputpic[0][0] = cal(0);
outputpic[0][1] = 0;
outputNum++;
int mask[9][2]={
{-1,-1},{-1,0},{-1,1},
{0, -1},{0, 0},{0,1},
{1, -1},{1,0}, {1,1}
};
int temp[2];
int jumpfromRow=-1;
int jumptoRow=-1;//-1表示不跳转
for (i=0, j=0; i<=endPos[0]; i++)//逐行计算
{
if (jumptoRow!=-1 && jumpfromRow!=-1)
{
i=jumptoRow;
jumpfromRow=-1;
jumptoRow=-1;
continue;
}
int rowPos = i*WIDTH;//行头的位置
if (rowPos==180)
{
cout<<"aaa"<
temp[1]=180;
insert(temp);
}
temp[0]= cal(rowPos);//计算行头
temp[1]=rowPos;
cout<
while (inputpic[j][1]
int row = inputpic[j][1]/WIDTH;
int col = inputpic[j][1]%WIDTH;
for (int k=0; k<9; k++)
{
temp[0] = cal(row+mask[k][0], col+mask[k][1]);
if (temp[0] != -1)
{
temp[1]=((row+mask[k][0])*WIDTH)+col+mask[k][1];
insert(temp);
}
}
int length;;
if (j
length = inputpic[j+1][1] - inputpic[j][1];
}
else
{
length = TotalNum-inputpic[j][1];
}
jumpfromRow = i+2;
jumptoRow = i+(length-(WIDTH-col))/WIDTH;
if (jumpfromRow>=jumptoRow)
{
jumpfromRow=-1;
jumptoRow=-1;
}
cout<
}
}
printf("%d\n", WIDTH);
for (i=0; i
printf("%d %d\n", outputpic[i][0],outputpic[i+1][1]-outputpic[i][1]);
}
printf("%d %d\n0 0\n", outputpic[i][0], TotalNum-outputpic[i][1]);
inputNum=0;
outputNum=0;
WIDTH=0;
TotalNum=0;
endPos[0]=0;
endPos[1]=0;
}
printf("0\n");
return 0;
}
int getInsertInd(int loc)
{
int i=outputNum-1;
while (outputpic[i][1]>=loc && i>=0)i--;
return i+1;
}
void insert(int temp[])//向outputpic中插入新的起始点,temp[0]表示Pixel,temp[1]表示起始位置
{
int index = getInsertInd(temp[1]);
if (index
outputpic[index][1]=temp[1];
return ;
}
else
{
if (index!=0 && temp[0] == outputpic[index-1][0])
{
//nothing
return;
}
}
for (int i=outputNum; i>index; i--)
{
outputpic[i][0] = outputpic[i-1][0];
outputpic[i][1] = outputpic[i-1][1];
}
outputpic[index][0] = temp[0];
outputpic[index][1] = temp[1];
outputNum++;
}
int cal(int row, int col)//计算(row, col)位置的最大值
{
if (row<0||row>endPos[0]||col<0 || col>endPos[1])
{
return -1;
}
return cal(row*WIDTH+col);
}
int cal(int loc)//计算Loc位置的最大值
{
int RCmask[8][2]={
{-1,-1},{-1,0},{-1,1},
{0, -1},{0,1},
{1, -1},{1,0}, {1,1}};
int mask[8]={-WIDTH-1, -WIDTH, -WIDTH+1,
-1, 1, WIDTH-1, WIDTH, WIDTH+1};
int val=getValue(loc);
int result=0;
int row = loc/WIDTH;
int col = loc%WIDTH;
for(int i=0; i<8; i++)
{
int temp = getValue(loc+mask[i], row+RCmask[i][0], col+RCmask[i][1]);
if (temp!=-1)
{
temp = abs(val-temp);
result = result>temp?result:temp;
}
}
return result;
}
int getValue(int loc, int row, int col)//专门用来处理越界问题
{
if (row<0||row>endPos[0]||col<0 || col>endPos[1])
{
return -1;
}
return getValue(loc);
}
int getValue(int loc)
{
if (loc<0 || loc>=TotalNum)
{
return -1;
}
int low=0, high = inputNum-1;
while(low<=high)
{
int mid=low+(high-low)/2;
if (inputpic[mid][1]<=loc)
{
if (inputpic[mid+1][1]>loc)
{
return inputpic[mid][0];
}
else
low=mid+1;
}
else
{
high=mid-1;
}
}
return -1;
}