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