2017年上海金马五校程序设计竞赛：Problem B : Sailing

Time Limit: 1 s

---

Description

Handoku is sailing on a lake at the North Pole. The lake can be considered as a two-dimensional square plane containing N × N blocks, which is shown in the form of string containing '*' and '#' on the map.

• * : a normal block;
• # : a block containing pack ice.

Handoku is at (1, 1) initially, and his destination is (N, N). He can only move to one of the four adjacent blocks. Sailing around pack ice is dangerous and stressful, so he needs power to remain vigilant. That means if he moves from a '*' block to a '#' block or moves from a '#' block to any another block, he needs to consume 1 unit power. In other cases, he can enjoy the scene on his boat without consuming any power.

Now Handoku wants to know how many units power will be consumed at least during his sailing on the lake.

 

Input

There are several test cases (no more than 20).
For each test case, the first line contains a single integer N (3 ≤ N ≤ 50), denoting the size of the lake. For the following N lines, each line contains a N-length string consisting of '*' and '#', denoting the map of the lake.

 

Output

For each test case, output exactly one line containing an integer denoting the answer of the question above.

 

Sample Input

3
**#
**#
*#*
3
##*
#*#
###
4
**##
#**#
##**
###*

 

Sample Output

2
4
0

题目意思：

给出一个N*N的地图，起点（1,1），终点（n,n）,每次只可以向四个方向走一个格子，地图只由两个字符组成 '*' 和 '#'。

从字符 ‘*’  走到字符'#'需要花费1秒时间，从字符'#'走到其他位置（无论那个位置字符是什么）也要花费1秒时间。其他

情况不花费时间。求从（1,1）走到（n,n）花费的最小时间。

解题思路：

这个题，上来第一个做的，感觉特别简单，BFS+优先队列然后标记每个点只走一次就行了，结果WA了4次，出师不利呀，又看了榜单，发现

大家都在WA，所以先隔过去了，但是最后感觉没有别的题能写出来了，又看到B题WA了好多次的人都A出来了，所以拐回去做。原来我的思路

是走过的地方不能再走，这样写每次提交都WA，就想了难道还能走回头路？但是觉得自己已经用了优先队列，感觉没道理WA。但是事实上是

那样做行不通（还好这次我没钻牛角尖，平时做题觉得思路没问题的时候，自己都死活不愿意改代码，而且也换题做，一般都是WA到死），所

以就试了一下走回头路，原来vis数组刷成0，走过的都标1。为了走回头路，新的代码把vis刷成-1，然后对于走过的点,vis放置走到该点的最小时

间，这样走到一个点，如果这个点没有访问过，即对应的vis是-1，则该点一定要进队，然后vis变成到达该点的时间。对于已经当过的点，vis数组

里面存放的是它上一次到达这个点的最小时间，现在又到了这个点，如果时间比vis里面的时间短，则更新vis，该点再次入队。这样处理后就可以

AC了，但是我没想出这样的测试数据，希望看到博客的人帮我想一组走回头路时间更短的数据。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;

const int maxn = 55;
char Map[maxn][maxn];
int vis[maxn][maxn];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}}; ///搜索方向上右下左
int n;
struct pos
{
    int x;
    int y;
    int power;
    friend bool operator < (pos a,pos b)
    {
        return a.power>b.power;
    }
};
///输入地图
int bfs()
{
    pos cur,nex;
    cur.x = 1;
    cur.y = 1;
    cur.power = 0;
    vis[cur.x][cur.y] = cur.power;
    priority_queue<pos>qu;
    qu.push(cur);
    while(!qu.empty())
    {
        cur = qu.top();
        qu.pop();
        if(cur.x == n && cur.y == n)
            return cur.power;
        for(int i = 0; i < 4; i++)
        {
            nex.x = cur.x + dir[i][0];
            nex.y = cur.y + dir[i][1];
            nex.power = cur.power;
            if(nex.x<1||nex.x>n||nex.y<1||nex.y>n) continue;
            if(Map[cur.x][cur.y]=='*')
            {
                if(Map[nex.x][nex.y]=='#')
                    nex.power++;
            }
            else
            {
                nex.power++;
            }
            if(vis[nex.x][nex.y]==-1)
            {
                vis[nex.x][nex.y] = nex.power;
                qu.push(nex);
            }
            else
            {
                if(nex.power<vis[nex.x][nex.y])
                {
                    vis[nex.x][nex.y] = nex.power;
                    qu.push(nex);
                }
            }
        }
    }
    return -1;
}
int main()
{
    while(~scanf("%d",&n))
    {
        getchar();
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
            {
                scanf(" %c",&Map[i][j]);
            }
        memset(vis,-1,sizeof(vis));
        int ans = bfs();
        printf("%d\n",ans);
    }
    return 0;
}