First One:
/* Bismillahir Rahmanir Rahim
Solution-Using BFS
*/
#include<bits/stdc++.h>
#define fi(n, m) for(int i=n; i<=m; i++)
#define fii(i, n, m) for(int i=n; i<=m; i++)
using namespace std;
vector<int>vt[405];
int sts[405], cnt[405];
int bfs(int st, int node, int en){
queue<int>q;
int vis[node+1];
fi(0, node) {vis[i]=0; cnt[i]=0;}
q.push(st);
while(!q.empty()){
int u=q.front();
q.pop();
fii(i, 0, vt[u].size()-1){
int v=vt[u][i];
if(!vis[v]){
if(v==en) return cnt[u]+1;
if(sts[v]==0){
cnt[v]=cnt[u]+1;
q.push(v);
}
vis[v]=1;
}
}
}
}
int main(){
int t, n, m, cs=1, ans;
cin>>t;
while(t--){
int a, b, c, h, cnt=0, a1, a2, a3;
cin>>m>>n;
fii(i, 1, m){
char ch;
cin>>ch;
cnt++;
if(ch=='#'||ch=='m') sts[cnt]=-1;
else if(ch=='h') {h=cnt; sts[cnt]=0;}
else if(ch=='a') {a=cnt; sts[cnt]=0;}
else if(ch=='b') {b=cnt; sts[cnt]=0;}
else if(ch=='c') {c=cnt; sts[cnt]=0;}
else sts[cnt]=0;
if(i>1){
vt[cnt].push_back(cnt-n);
vt[cnt-n].push_back(cnt);
}
fii(j, 2, n){
cin>>ch;
cnt++;
if(ch=='#'||ch=='m') sts[cnt]=-1;
else if(ch=='h') {h=cnt; sts[cnt]=0;}
else if(ch=='a') {a=cnt; sts[cnt]=0;}
else if(ch=='b') {b=cnt; sts[cnt]=0;}
else if(ch=='c') {c=cnt; sts[cnt]=0;}
else sts[cnt]=0;
vt[cnt].push_back(cnt-1);
vt[cnt-1].push_back(cnt);
if(i>1){
vt[cnt].push_back(cnt-n);
vt[cnt-n].push_back(cnt);
}
}
}
a1=bfs(a, n*m, h);
a2=bfs(b, n*m, h);
a3=bfs(c, n*m, h);
ans=max(a1, max(a2, a3));
cout<<"Case "<<cs++<<": "<<ans<<endl;
fi(0, n*m)vt[i].clear();
}
return 0;
}
|
Second One:
/* Bismillahir Rahmanir Rahim
Solution-Using BFS
*/
#include<bits/stdc++.h>
#define fi(n, m) for(int i=n; i<=m; i++)
#define fii(i, n, m) for(int i=n; i<=m; i++)
using namespace std;
queue<int>q;
int sts[401], cnt[401], m, n;
int bfs(int st, int node, int en){
while(!q.empty()) q.pop();
int vis[node+1];
fi(0, node) {vis[i]=0; cnt[i]=0;}
q.push(st);
while(!q.empty()){
int u=q.front();
q.pop();
if(u>n){
int v=u-n;
if(!vis[v]){
if(v==en) return cnt[u]+1;
if(sts[v]==0){
cnt[v]=cnt[u]+1;
q.push(v);
}
vis[v]=1;
}
}
if(u%n!=1){
int v=u-1;
if(!vis[v]){
if(v==en) return cnt[u]+1;
if(sts[v]==0){
cnt[v]=cnt[u]+1;
q.push(v);
}
vis[v]=1;
}
}
if(u%n!=0){
int v=u+1;
if(!vis[v]){
if(v==en) return cnt[u]+1;
if(sts[v]==0){
cnt[v]=cnt[u]+1;
q.push(v);
}
vis[v]=1;
}
}
if(u<=n*(m-1)){
int v=u+n;
if(!vis[v]){
if(v==en) return cnt[u]+1;
if(sts[v]==0){
cnt[v]=cnt[u]+1;
q.push(v);
}
vis[v]=1;
}
}
}
}
int main(){
int t, cs=1, ans, a, b, c, h, cnt, a1, a2, a3;
char ch;
cin>>t;
while(t--){
cnt=0;
cin>>m>>n;
fii(i, 1, m){
fii(j, 1, n){
cin>>ch;
cnt++;
if(ch=='#'||ch=='m') sts[cnt]=-1;
else if(ch=='h') {h=cnt; sts[cnt]=0;}
else if(ch=='a') {a=cnt; sts[cnt]=0;}
else if(ch=='b') {b=cnt; sts[cnt]=0;}
else if(ch=='c') {c=cnt; sts[cnt]=0;}
else sts[cnt]=0;
}
}
a1=bfs(a, n*m, h);
a2=bfs(b, n*m, h);
a3=bfs(c, n*m, h);
ans=max(a1, max(a2, a3));
cout<<"Case "<<cs++<<": "<<ans<<endl;
}
return 0;
}
|
No comments:
Post a Comment