3142456_ac_110ms_2724k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <iostream>
#include <queue>
#include <algorithm>
#define MAX 21
#define SIZE 104
using namespace std;

int R, C;
char table[MAX][MAX];

struct node
{
	int h[26];
	int r, c;
	int step;
};

queue <node> que;

bool valid(int r,int c)
{
	return r >= 0 && r < R && c >= 0 && c < C;
}

void bfs()
{
	int max;
	node t;
	const int mov[][2] = {{0,1},{0,-1},{1,0},{-1,0}};

	max = 1;
	t.r = t.c = 0;
	memset(t.h,0,SIZE);
	t.step = 1;
	t.h[table[t.r][t.c]-'A'] = 1;
	que.push(t);
	while(!que.empty())
	{
		t = que.front();
		que.pop();
		for(int i = 0; i < 4; i++)
		{
			node p = t;
			int r = p.r + mov[i][0];
			int c = p.c + mov[i][1];
			if(valid(r, c)&&p.h[table[r][c]-'A']==0)
			{
				p.h[table[r][c]-'A'] = 1;
				p.r = r;
				p.c = c;
				p.step = t.step + 1;
				if(p.step > max)
				{
					max = p.step;
				}
				que.push(p);
			}
		}
	}
	printf("%d\n",max);
}

int main()
{
	cin >> R >> C;
	for(int i = 0; i < R; i++)
	{
		cin >> table[i];
	}
	bfs();
	return 0;
}