UVA - 160 Patrol Robot

客官°小女子只卖身不卖艺 2021-09-29 14:18 174阅读 0赞

/\*  
题目链接：  
https://uva.onlinejudge.org/index.php?option=com\_onlinejudge&Itemid=8&page=show\_problem&problem=4475  
  
  
知识点：  
带状态的 bfs  
通过增加数组维度来实现

\*/

#include <iostream>
    #include <cstring>
    #include <queue>
    #define rep(i, n) for ( int i = 0; i < (n); i++ )
    using namespace std;
    const int N = 25;
    int m, n, k, ans;
    int dxy[4][4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
    int map[N][N], vis[N][N][N];
    // vis 加第三个维度，其实是为了区分状态，比如同样是到达 (5,5) 这个位置，如果是已经连续通过 3 个障碍，和连续通过了2个障碍的时候，这两种情况，虽然最后都是到达 (5,5)，但这其实是两种不同的状态
    // 所以，加入的第三个维度，就是为了记录，当前位置剩余的 "可连续通过的障碍数" 
    
    struct node
    {
    	int x, y, cnt, k; // cnt 保存的是从起点到该结点的最短路径长度，k保存的是当前该结点剩余的 "可连续穿过障碍数"
    	node(int x1, int y1, int c, int k1)
    	{
    		x = x1, y = y1, cnt = c, k = k1;
    	}
    };
    
    void init()
    {
    	memset(map, 0, sizeof(map));
    	memset(vis, 0, sizeof(vis));
    	cin >> n >> m >> k;
    	
    	rep(i, n) rep(j, m) cin >> map[i][j];
    }
    
    void bfs()
    {
    	queue<node> q;
    	node u(0, 0, 0, k);
    	vis[0][0][k] = 1;
    	q.push(u); 
    	
    	while (!q.empty())
    	{
    		u = q.front();
    		q.pop();
    		
    		if (u.x == n - 1 && u.y == m - 1)
    		{
    			ans = u.cnt;
    			return;
    		}
    		
    		if (u.k >= 0)
    		{
    			rep(i, 4)
    			{
    				node v(u.x + dxy[i][0], u.y + dxy[i][1], u.cnt + 1, u.k - 1);
    				if (!map[v.x][v.y]) v.k = k; //如果当前走的不是障碍处，则重置 k
    				
    				if ( v.k >= 0 && v.x >= 0 && v.x < n && v.y >= 0 && v.y < m && !vis[v.x][v.y][v.k] )
    				{
    					q.push(v);
    					vis[v.x][v.y][v.k] = 1;
    				}
    			}
    		}
    	}
    	ans = -1;
    }
    
    int main()
    {
    	int t;
    	cin >> t;
    	while (t--)
    	{
    		init();
    		bfs();
    		cout << ans << endl;
    	}
    	return 0;
    }

转载于:https://www.cnblogs.com/mofushaohua/p/7789351.html