一个每块地板标记着0~9某个数字的迷宫,其中标记1的地板不可以走,标记2~9的地板可以不花时间地跳到任意相同数字的位置,也可以和标记0的地板一样向前后左右任意方向花1个单位时间移动1的距离。给出起点和终点,求起点到终点的最短时间。

一眼望去就想到了广搜 可是编完总是W~~最后发现广搜的时候按步入队列时候可能会发现以下情况

1;1个点入过了队列 可是可以从另1个点跳过去(步数少1)

2:上一种情况的前提下 1个点先到达了终点 而跳过的点接着到达(步数少1)

改掉就过了~~~比赛结束前13秒过的,唏嘘。。

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <stdio.h>  
#include <stdlib.h>  
#include <iostream>  
#include <string.h>  
#include <limits.h>  
#include <queue> 
using namespace std; 
queue<int>Q;
int b1,b2,n;
char l[200][200][2];
int s[200][200];
void suan(int a,int b)
{
    int i,j;
    Q.push(a);
    Q.push(b);
    while(!Q.empty())
    {
        a=Q.front();
        Q.pop();
        b=Q.front();
        Q.pop();
        if(a==b1&&b==b2)
        {   if(l[a+1][b][0]!='1'&&(s[a+1][b]+1)<s[a][b]&&s[a+1][b]!=0)
                s[a][b]=s[a+1][b]+1;
            if(l[a][b+1][0]!='1'&&(s[a][b+1]+1)<s[a][b]&&s[a][b+1]!=0)
                s[a][b]=s[a][b+1]+1;
            if(l[a-1][b][0]!='1'&&(s[a-1][b]+1)<s[a][b]&&s[a-1][b]!=0)
                s[a][b]=s[a-1][b]+1;
            if(l[a][b-1][0]!='1'&&(s[a][b-1]+1)<s[a][b]&&s[a][b-1]!=0)
                s[a][b]=s[a][b-1]+1;
            printf("%d\n",s[a][b]);
            return ;
        }
        if(l[a][b][0]>='2'&&l[a][b][0]<='9')
        {
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=n;j++)
                {
                    if(l[a][b][0]==l[i][j][0]&&(a!=i||b!=j))
                {
                    if(s[a][b]<s[i][j]||s[i][j]==0)
                    {
                    l[i][j][1]='1';
                    s[i][j]=s[a][b];
                    Q.push(i);
                    Q.push(j);
                    }
                }   
            }
        }
        }
        if(l[a][b+1][0]!='1'&&l[a][b+1][1]!='1')
        {
        l[a][b+1][1]='1';
        s[a][b+1]=s[a][b]+1;
        Q.push(a);
        Q.push(b+1);
        }
        if(l[a+1][b][0]!='1'&&l[a+1][b][1]!='1')
        {
        l[a+1][b][1]='1';
        s[a+1][b]=s[a][b]+1;
        Q.push(a+1);
        Q.push(b);
        }
        if(l[a][b-1][0]!='1'&&l[a][b-1][1]!='1')
        {
        l[a][b-1][1]='1';
        s[a][b-1]=s[a][b]+1;
        Q.push(a);
        Q.push(b-1);
        }
        if(l[a-1][b][0]!='1'&&l[a-1][b][1]!='1')
        {
        l[a-1][b][1]='1';
        s[a-1][b]=s[a][b]+1;
        Q.push(a-1);
        Q.push(b);
        }
    }   
    printf("Oh No!\n");
    return ;
}
int main()
{
    int i,j,a1,a2;
    while(scanf("%d",&n)!=EOF)
    {
        while(!Q.empty()) 
        
            Q.pop();
        }
        memset(l,0,sizeof(l));
        memset(s,0,sizeof(s));
        for(i=0;i<=n+1;i++)
        {
            l[0][i][0]='1';
            l[n+1][i][0]='1';
            l[i][0][0]='1';
            l[i][n+1][0]='1';
        }
        getchar();
        for(i=1;i<=n;i++)
        {   for(j=1;j<=n;j++)
            {   
                scanf("%c",&l[i][j][0]);
                if(l[i][j][0]=='S'||l[i][j][0]=='s')
                {
                    a1=i;
                    a2=j;
                }
                if(l[i][j][0]=='E'||l[i][j][0]=='e')
                {
                    b1=i;
                    b2=j;
                }
            }
        getchar();
        }
        l[a1][a2][1]='1';
        s[a1][a2]=0;
        suan(a1,a2);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation