米哈游0904

编程第三题：
在一个n*m（n,m<=300）大小的盘子上，小米从(0,0)处出发，开图中的唯一一个宝箱（@），但是地面是光滑（.表示地面）的，每次移动，只能碰到边界或者障碍物（#）或者宝箱（@）才能停下。问最少需要移动几次？
输入样例：

4 4
...#
.@..
....
#...

输出：

4

思路:如果贪心的话，可能得到的不是最优解，因此使用dfs。那么有两个问题：
1.如何标记当前点可以到达的下一个点。这里可以使用一个四维数组来记录每个位置上下左右可以到达的下一个位置。
2.如何标记一个点是否已经经过，避免重复？仍然选用vis数组。二维即可。（做题时使用了是标记i,j位置加方向，效果不如人意）。
代码：

#include <iostream>
#include <string>
#include <vector>
#include <climits>
using namespace std;
int ans = INT_MAX, n, m;
vector<int> off({-1, 0, 1, 0, -1});
vector<vector<vector<vector<int>>>> urdl;  // urdl代表四个方向可以碰停的下一个地点
vector<vector<bool>> vis;
inline bool good(int i, int j)
{
    if (i < 0 || i >= n || j < 0 || j >= m)
        return false;
    return true;
}
inline void dfs(vector<string> &a, int i, int j, int cnt)
{
    if (cnt > ans) 
        return;
    for (int k = 0; k < 4; k++)
        if (good(i + off[k], j + off[k + 1]) && a[i + off[k]][j + off[k + 1]] == '@')
        {
            ans = min(ans, cnt);
            return;
        }
    vis[i][j] = true;
    for (int k = 0; k < 4; k++)
        if (!(urdl[i][j][k][0] == i && urdl[i][j][k][1] == j) && !vis[urdl[i][j][k][0]][urdl[i][j][k][1]])
            dfs(a, urdl[i][j][k][0], urdl[i][j][k][1], cnt + 1);
    vis[i][j] = false;
}
int main()
{
    cin >> n >> m;
    vector<string> a(n);    // 以string数组储存
    for (int i = 0; i < n; i++)
        cin >> a[i];
    vis = vector<vector<bool>>(n, vector<bool>(m, false));    
    urdl = vector<vector<vector<vector<int>>>>(n, vector<vector<vector<int>>>(m, vector<vector<int>>(4, vector<int>(2))));
    for (int i = 0; i < n; i++)    // 初始化下一个位置
    {
        for (int j = 0; j < m; j++)
        {
            if (a[i][j] == '.')
            {
                urdl[i][j][0][0] = i;
                urdl[i][j][0][1] = j;
                urdl[i][j][1][0] = i;
                urdl[i][j][1][1] = j;
                urdl[i][j][2][0] = i;
                urdl[i][j][2][1] = j;
                urdl[i][j][3][0] = i;
                urdl[i][j][3][1] = j;
                while (urdl[i][j][0][0] >= 0 && a[urdl[i][j][0][0]][j] == '.')
                    urdl[i][j][0][0]--;
                urdl[i][j][0][0]++;
                while (urdl[i][j][1][1] < m && a[i][urdl[i][j][1][1]] == '.')
                    urdl[i][j][1][1]++;
                urdl[i][j][1][1]--;
                while (urdl[i][j][2][0] < n && a[urdl[i][j][2][0]][j] == '.')
                    urdl[i][j][2][0]++;
                urdl[i][j][2][0]--;
                while (urdl[i][j][3][1] >= 0 && a[i][urdl[i][j][3][1]] == '.')
                    urdl[i][j][3][1]--;
                urdl[i][j][3][1]++;
            }
        }
    }

    dfs(a, 0, 0, 0);
    cout << (ans == INT_MAX ? -1 : ans) << endl;
    return 0;
}

这是对考试中我编辑的代码的梳理版。
考虑到效率优化，可以再加一个dp数组，记录已经搜索过的位置。而且，dp数组还可以与vis数组合并。所以，最后只需要改个类型就好了。