| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
bfs#include<iostream>
#include<queue>
using namespace std;
int r,c;
char map[100][100];
int move[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
struct note
{
int x;
int y;
int count;
bool used[26];
};
void bfs()
{
int max=0;
queue<note> q;
int front=0,rear=0;
note current,next;
current.x=0,current.y=0;
current.count=1;
memset(current.used,false,sizeof(current.used));
current.used[map[0][0]-'A']=true;
q.push(current);
while(!q.empty())
{
current=q.front();
q.pop();
if(current.count>max)
max=current.count;
int i;
for(i=0;i<4;i++)
{
next.x=current.x+move[i][0];
next.y=current.y+move[i][1];
int j;
for(j=0;j<26;j++)
{
next.used[j]=current.used[j];
}
if(next.x>=0&&next.x<r&&next.y>=0&&next.y<c&&!next.used[map[next.x][next.y]-'A'])
{
next.count=current.count+1;
next.used[map[next.x][next.y]-'A']=true;
q.push(next);
}
}
}
printf("%d\n",max);
}
int main()
{
scanf("%d%d",&r,&c);
int i;
for(i=0;i<r;i++)
{
cin>>map[i];
}
bfs();
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator