Jeopardy of Dropped Balls(模拟+优化)

题目链接：Problem - J - Codeforces

题目中文意思：

查内克先生有一个新游戏叫丢球。最初，Chanek先生有一个尺寸为n×m的网格a

每个单元格（x，y）包含一个整数ax，y，表示球移动的方向。

ax，y=1-球将向右移动（下一个单元格为（x，y+1））；

ax，y=2-球将移动到底部（下一个单元格为（x+1，y））；

ax，y=3-球将向左移动（下一个单元格为（x，y−1)).

每次球离开单元格（x，y），整数ax，y将变为2。查内克先生将从第一排开始，依次在c1、c2、…、ck th（1）上落下k个球≤词≤m） 列。

确定每个球将在哪列结束（球离开网格后的位置）。

分析：看到数据范围后就知道这道题肯定不是暴力模拟，这样必然会TLE，我们需要对朴素做法及进行一定的优化，具体优化方法就是我们用一个数组记录一下每一列自下向上的连续的2的个数，这样我们就可以不把模拟进行完就知道结果了，我们对这个数组进行更新时，不能每次都从最下方开始尝试，容易发现这个数组每次更新不会变小，要么不变要么比原来更大，举个例子，假如flag[5]=3,代表第五列自下向上有3个连续的2，则下次更新flag[5]时，我们可以直接从倒数第四行开始，当遍历到第一个不是2的直接跳出，这样保证了每次更新都是有效更新，那如何用这个数组进行优化呢？比如flag[3]=4,总共有6行，我们现在遍历到第三行第三列，那我们就知道了他接下来都是直接向下，这样就可以省去剩下的模拟过程了，具体实现看代码：

#include
#include
#include
#include
using namespace std;
int flag[1005],mp[1005][1005];
//flag[i]记录的是第i列从下往上数连续的2的个数 
int main()
{
	int n, m, k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&mp[i][j]);
	for(int j=m;j>=1;j--)//预处理每一列的自下向上的连续的2的个数 
	{
		int i=n;
		while(i)
		{
			if(mp[i][j]!=2) break;
			flag[j]++; 
			i--;
		}
	}
	int nowx=1,nowy;//当前所在的行和列 
	for(int i=1;i<=k;i++)
	{
		scanf("%d",&nowy);
		nowx=1;
		int fflag=-1;
		while(nowx<=n)
		{
			int t=mp[nowx][nowy];
			mp[nowx][nowy]=2;
			if(nowx+flag[nowy]>n) //代表从当前行开始可以直接下落结束 
			{
				printf("%d ",nowy);//输出下降时所在的列 
				fflag=1;
				break;
			}
			if(t==1) nowy++;
			if(t==2) nowx++;
			if(t==3) nowy--;
		}
		if(fflag==-1) printf("%d ",nowy);//如果最后一行初始时无2，则在while循环中不会输出，注意特判 
		for(int i=1;i<=m;i++)//这两重循环最多执行n*m次，仔细体会 
		{
			while(flag[i]