1889. Max’s game

TAG 种子染色 flood fill 队列 数据结构

使用类似种子染色的方法，从起点开始染色，使用队列保证花费小的先染到。

//1.07 sec  	1476 KB  	2839 Bytes
#include <stdio.h>
#include <queue>
#include <memory.h>
 
using namespace std;
const int DY[]={0,  1, 0, -1};
const int DX[]={-1, 0, 1, 0};
struct point
{
	int x,y;
	bool operator==(const point &p) const
	{
		return x==p.x && y==p.y;
	}
};
point start,end;
int row, col;
char map[500][501];
int order[500][500];
bool inRange(point p)
{
    if ( p.x>=0 && p.x<row && p.y>=0 && p.y<col)
    {
		return true;
    }
	return false;
}
void fill(point  pt)
{
	queue<point> qu1;
	qu1.push(pt);
 
	while ( !qu1.empty() ) //设此时qu1中的元素为A
	{
		point tmp1=qu1.front();
		
	    queue<point> qu2(qu1);

		while ( !qu2.empty() )//对A中相邻颜色相同的染色
		{
			point tmp2=qu2.front();
			qu2.pop();
			for (int i=0; i<4; ++i)
			{
				point tmp;
				tmp.x=tmp2.x+DX[i];
				tmp.y=tmp2.y+DY[i];
				if (   inRange(tmp) 
					&& map[ tmp.x ][ tmp.y]==map[ tmp2.x ][ tmp2.y]
					&& order[ tmp.x ][tmp.y ]==0 )
				{
					order[ tmp.x ][tmp.y ]=order[ tmp2.x ][tmp2.y ];
					if ( tmp==end )
					{
						return;      //have found the ans.
					}
					qu1.push(tmp);
					qu2.push(tmp);
				}
			}
		}

		while ( !qu1.empty() )//与A相邻但颜色不同的入列，并去掉A
		{
			point tar=qu1.front();
			if ( order[tmp1.x][tmp1.y] != order[tar.x][tar.y] )
			{
				break;
			}
			qu1.pop();
			for (int i=0; i<4; ++i)
			{
				point tmp;
				tmp.x=tar.x+DX[i];
				tmp.y=tar.y+DY[i];
				if (   inRange(tmp) 
					&& map[ tmp.x ][ tmp.y]!=map[ tar.x ][ tar.y]
					&& order[ tmp.x ][tmp.y ]==0 )
				{
					order[ tmp.x ][tmp.y ]=order[ tar.x ][tar.y ]+1;
		         	if ( tmp==end )
					{
						return;      //have found the ans.能有效减少时间
					}
					qu1.push( tmp );
				}
			}
		}
		

	}
}


int main(int argc, char *argv[])
{
	while ( scanf("%d%d", &row, &col)!=EOF )
	{
		for (int i=0; i<row; ++i)
		{
			scanf("%s", map[i]);
		}
		
		
		scanf("%d%d%d%d", &start.x, &start.y,  &end.x, &end.y);
		
		memset( order, 0, sizeof(order) );
		order[start.x][start.y]=1;
    	fill(start);
 /*
   for (int i=0; i<row; ++i)
   {
       for (int j=0; j<col; ++j)
         printf("%d  ", order[i][j]);
         
       printf("/n");
   }
    */
		printf("%d/n", order[end.x][end.y]-1 );
	}
	
	return 0;
}