zoj1479 dweep soj1106 搜索
【大意】
在n*m(n<=20,m<=20)的网格中，有若干的激光发射器，激光发射器面朝上或者下或左或右，激光被终止于激光发射器或者障碍，somebody想从网格的A点走到B点，somebody可以从8个方向走，但她不能连续在有激光的地方走，也就是说她走得路径的相邻2格内至多只有一个格子上有激光，问路径上最少有几个格子被激光照射。
【分析】
典型的bfs。
注意激光发射器和障碍一样不能走。
在扩展节点的时候当前节点有激光时不扩展下一个也有激光的节点。
路径记录当前路径走过的有激光的格子数目。
也可以加点启发式信息，记h为从当前节点到目标节点最少路过的有激光的节点，可以用floyd先计算出任意2个节点的最少激光节点路径（效率过低，反倒更慢了。。），再用A*。
【参考代码】
#include <stdio.h>#include <ctype.h>#include <string.h>#include <map>#include <functional>#include <algorithm>#include <queue>using namespace std;inline bool get(int &t){ bool flag = 0 ; char c; while(!isdigit(c = getchar())&&c!='-') if( c == -1 ) break ; if( c == -1 ) return 0 ; if(c=='-') flag = 1 , t = 0 ; else t = c ^ 48; while(isdigit(c = getchar())) t = (t << 1) + (t << 3) + (c ^ 48) ; if(flag) t = -t ; return 1 ;}typedef pair<int,int> pii ;const int INF = 0x1fffffff ;const int maxn = 22 ;int n , m , sx , sy , ex , ey , border[maxn][maxn] , dist[maxn][maxn] , rep[128] ;char dir[maxn][maxn] ;bool vis[maxn][maxn] ;const int cx[] = {1,0,0,-1} ;const int cy[] = {0,1,-1,0} ;const int ccx[] = {-1,-1,-1,0,0,1,1,1};const int ccy[] = {-1,0,1,-1,1,-1,0,1};inline void init() //set laser{ int i , j , k , x , y ; for( i = 1 ; i <= n ; i++) for( j = 1 ; j <= m ; j++) dist[i][j] = INF ; dist[sx][sy] = 0 ; for( i = 1 ; i <= n ; i++) { for( j = 1 ; j <= m ; j++) if( border[i][j] == 1 && dir[i][j] != -1 ) { k = dir[i][j] ; x = i + cx[k] ; y = j + cy[k] ; border[i][j] = 2 ;while ( x >= 1 && x <= n && y >= 1 && y <= m && border[x][y] != 2 ) { border[x][y] = 1 ; x += cx[k] ; y += cy[k] ; } } }}inline void solve(){ init(); queue<pii> q ; q.push(make_pair(sx,sy)); memset(vis,0,sizeof(vis)); vis[sx][sy] = 1 ; while(!q.empty()) { int i , j , k , x , y , nx , ny ; x = q.front().first ; y = q.front().second ; vis[x][y] = 0 ; q.pop(); if( border[x][y] == 0 ) { for( k = 0 ; k < 8 ; k++) { nx = x + ccx[k] ; ny = y + ccy[k] ; if ( nx >= 1 && nx <= n && ny >= 1 && ny <= m ) { if( border[nx][ny] == 0 && dist[nx][ny] > dist[x][y] ) { dist[nx][ny] = dist[x][y] ; if(!vis[nx][ny]) q.push(make_pair(nx,ny)),vis[nx][ny]=1; } else if( border[nx][ny] == 1 && dist[nx][ny] > dist[x][y] + 1 ) { dist[nx][ny] = dist[x][y] + 1 ; if(!vis[nx][ny]) q.push(make_pair(nx,ny)),vis[nx][ny]=1; } } } } else { for( k = 0 ; k < 8 ; k++) { nx = x + ccx[k] ; ny = y + ccy[k] ; if ( nx >= 1 && nx <= n && ny >= 1 && ny <= m && border[nx][ny] == 0 && dist[nx][ny] > dist[x][y] ) { dist[nx][ny] = dist[x][y] ; if(!vis[nx][ny]) q.push(make_pair(nx,ny)),vis[nx][ny]=1; } } } } printf("%d\n",dist[ex][ey]==INF?-1:dist[ex][ey]);}int main(){ int i , x , y , j , k ; char op[10]; rep['d'] = 0 ; rep['l'] = 2 ; rep['u'] = 3 ; rep['r'] = 1 ; while (get(n)) { get(m); get(sx); get(sy); get(ex); get(ey); get(k); memset(border,0,sizeof(border)); for( i = 0 ; i < maxn ; i++)for( j = 0 ; j < maxn ; j++)dir[i][j] = -1 ; while(k--) { get(x); get(y); scanf("%s",op); if( op[0] != 'B' ) //laser { dir[x][y] = rep[op[0]] ; border[x][y] = 1 ; } else border[x][y] = 2 ; //obstacle } solve(); }}
