BFS做法+图论抽象分析
1 :分离抽象点
判断点的入度和出度:1 边界点的出入度,2 内部点的出入度。
2 :区分简单图,复杂图
判断图中点之间的关系,简单图(n个链+环)
环:图中的每个点,入度+出度都是2;
链:图中边界点的度为1,中间点度为2.
(本题要注意,控制方向的方向数组改变方向时候要保持一致)
3 :目标是最短路,最长路,最小生成树......
用不同算法(dijkstra,spfa,ballman ford.....)
#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
using namespace std;
const int N=1e3+10;
struct node
{
int x,y;
char c;
int u;
};
char g[N][N];
int t1[4]={3,2,1,0},t2[4]={1,0,3,2};
int dy[4]={0,-1,0,1},dx[4]={1,0,-1,0};
int n,m;
int bfs(int x1,int y1,int u1)
{
queue<node> q;
q.push({x1,y1,g[x1][y1],u1});
int d=1;
while(q.size())
{
auto t=q.front();
q.pop();
int a,b;
int u;
if(t.c=='\\')
{
a=t.x+dx[t1[t.u]];
b=t.y+dy[t1[t.u]];
u=t1[t.u];
}
else
{
a=t.x+dx[t2[t.u]];
b=t.y+dy[t2[t.u]];
u=t2[t.u];
}
if(a<0||a>=n||b>=m||b<0) return d;
d=d+1;
q.push({a,b,g[a][b],u});
}
return d;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%s",g[i]);
int ans=0;
for(int i=0;i<m;i++)
{
ans=max(ans,bfs(0,i,0));
ans=max(ans,bfs(n-1,i,2));
}
for(int i=0;i<n;i++)
{
ans=max(ans,bfs(i,0,3));
ans=max(ans,bfs(i,m-1,1));
}
printf("%d",ans);
return 0;
}
orz
cout << % * n;