P2937 [USACO09JAN]Laserphones S

题意翻译

img

输入 #1

1
2
3
4
5
6
7
8
9
7 8 
....... 
......C 
......* 
*****.* 
....*.. 
....*.. 
.C..*.. 
.......

输出 #1

1
3
  1. 建立分层图跑最短路
  2. dfs
  3. lca ？
  4. bfs: $low[x][y][f]$ 表示到达（x，y）方向为 f 时的最少转弯次数。在某个点，有三个转移状态，向左向右或前进一步，用优先队列保存点的状态，转弯次数少的优先 (点上旋转不能转已经转过的方向，但是走上来的时候可惜更新代价)。这样第一个到达终点的即最优解.(hushuo ，糊了一个代码过了，感觉不对，但是不会证明…)
  5. bfs:按这样的顺序入队：如果点从横向（f=1）拓展而来，则遍历此点时，按纵向（f=2）拓展所有可以到达的点（step + 1）,纵向同理。由 bfs 的性质可知，第一次到达终点的即最小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//AC
const int INF=0x3f3f3f3f;
const int MAX=100+10;
int n,m,fx,fy;
bool vis[MAX][MAX];
char a[MAX][MAX];
bool judge(int x,int y){
	if(x<1 || x>n || y<1 ||y>m) return false;
	return true;
}
struct node{
	int x,y,f,step;
	node(int _x,int _y,int _f,int _step){
		x=_x;y=_y;f=_f;step=_step;
	}
};
int bfs(int x,int y,int f){
	queue<node> q;
	q.push(node(x,y,f,0));
	mem(vis,0);
	vis[x][y]=1;
	int cnt =0 ,tx,ty;
	while(!q.empty()){
		node t= q.front();
		q.pop();
		if(!(t.x == fx && t.y == fy) && a[t.x][t.y]=='C') return t.step;
		if(t.f==1){ // row
			tx = t.x -1 ,ty = t.y;
			while(judge(tx,ty) && !vis[tx][ty] && a[tx][ty]!='*'){
				q.push(node(tx,ty,2,t.step+1));
				vis[tx][ty]=1;
				tx--;
			}
			tx = t.x +1 ;
			while(judge(tx,ty)&& !vis[tx][ty]  && a[tx][ty]!='*'){
				q.push(node(tx,ty,2,t.step+1));
				vis[tx][ty]=1;
				tx++;
			}
		}else { //col
			tx = t.x ,ty = t.y - 1;
			while(judge(tx,ty) && !vis[tx][ty] && a[tx][ty]!='*'){
				q.push(node(tx,ty,1,t.step+1));
				vis[tx][ty]=1;
				ty--;
			}
			ty = t.y +1 ;
			while(judge(tx,ty) && !vis[tx][ty] && a[tx][ty]!='*'){
				q.push(node(tx,ty,1,t.step+1));
				vis[tx][ty]=1;
				ty++;
			}
		}
	}
	return INF;
}
int main(){
	freopen("in","r",stdin);
	sf(m);sf(n);
	fi(i,1,n+1) scanf("%s",a[i]+1);
	fi(i,1,n+1) fi(j,1,m+1)
		if(a[i][j]=='C') {
			fx = i; fy = j;
		}
	pf(min(bfs(fx,fy,1),bfs(fx,fy,2))-1);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// ganjuecuodanshique aclededaima
const int INF=0x3f3f3f3f;
const int MAX=100+10;
int n,m,fx,fy,ans,aw[4][2]={-1,0,0,1,1,0,0,-1};
char a[MAX][MAX];
bool vis[MAX][MAX][4];
int low[MAX][MAX][4];
struct node{
	int x,y,f;
	node(int _x,int _y,int _f ){
		x=_x;y=_y;f=_f;
	}
	bool operator < (const node &a) const {
		return low[x][y][f] > low[a.x][a.y][a.f];
	}
};
bool judge(int x,int y){
	if(x<1 || x>n || y<1 ||y>m) return false;
	return true;
}
void bfs(int x,int y){
	priority_queue<node> q;
	mem(vis,0);mem(low,0x3f);
	q.push(node(x,y,0));q.push(node(x,y,1));
	q.push(node(x,y,2));q.push(node(x,y,3));
	vis[x][y][0]=vis[x][y][1]=vis[x][y][2]=vis[x][y][3]=1;
	low[x][y][0]=low[x][y][1]=low[x][y][2]=low[x][y][3]=0;
	while(!q.empty()){
		node t =q.top();
		q.pop();
		if(!(t.x == fx && t.y == fy) && a[t.x][t.y]=='C'){
			ans = low[t.x][t.y][t.f];
			return;
		}
		if(!vis[t.x][t.y][(t.f+5)%4]){ // right
			q.push(node(t.x,t.y,(t.f+5)%4));
			vis[t.x][t.y][(t.f+5)%4] = 1;
			low[t.x][t.y][(t.f+5)%4] = low[t.x][t.y][t.f] + 1;
		}
		if(!vis[t.x][t.y][(t.f+3)%4]){ //left
			q.push(node(t.x,t.y,(t.f+3)%4));
			vis[t.x][t.y][(t.f+3)%4] = 1;
			low[t.x][t.y][(t.f+3)%4] = low[t.x][t.y][t.f] + 1;
		}
		int tx = t.x +aw[t.f][0],ty = t.y +aw[t.f][1]; //forward
		if(judge(tx,ty) && a[tx][ty]!='*' && low[tx][ty][t.f] > low[t.x][t.y][t.f]){
			q.push(node(tx,ty,t.f));
			vis[tx][ty][t.f] = 1;
			low[tx][ty][t.f] = low[t.x][t.y][t.f];
		}
	}
}
int main(){
	freopen("in","r",stdin);
	sf(m);sf(n);
	fi(i,1,n+1) scanf("%s",a[i]+1);
	fi(i,1,n+1) fi(j,1,m+1)
		if(a[i][j]=='C') {
			fx = i; fy = j;
		}
	ans = INF;
	bfs(fx,fy); 
	pf(ans);
	return 0;
}