C++

Forum

 
Testing

jmpt (13)
If you can see this, please tell me. I seem to not be able to write!!!
jmpt (13)
Nevermind. Preview seems not to work. Please ignore.
George P (5600)
With new topic posts none of the functions, format and preview, work.

Save the opening post, then add or edit the post and they will.

This is a problem that has been known for a long time. The admin has been contacted about it many times before. So far nothing has been done to fix it.
Last edited on
epdlqlemqpzja1234 (2)
Test Group
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
 
#include<iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

int MIN = 10000;
int Y;
int X;
int mine[100+10][100+10];
vector<pair<int, int>> adj[100+10][100+10];

int bfs(int y, int x)
{
    queue<pair<int, int>> que; 
    int visited[100+10][100+10]={0,};

    que.push(make_pair(y,x));
    visited[y][x] = 1;
    
    while(!que.empty()){
        pair<int,int> v = que.front();
        que.pop();
        
        if(v.first == Y && v.second == X){
            if(MIN > visited[v.first][v.second]){
                MIN = visited[v.first][v.second];
            }
        }

        for(size_t i=0; i<adj[v.first][v.second].size(); ++i){
            if(visited[adj[v.first][v.second][i].first][adj[v.first][v.second][i].second] == 0)
                que.push(make_pair(adj[v.first][v.second][i].first, adj[v.first][v.second][i].second));
                visited[adj[v.first][v.second][i].first][adj[v.first][v.second][i].second] = visited[v.first][v.second]+1;
                
        }
    }

    // for(int y=1; y<=Y; ++y){
    //     for(int x=1; x<=X; ++x){
    //         printf("%d ", visited[y][x]);
    //     }
    //     printf("\n");
    // }

    return MIN;
}

int main()
{
    scanf("%d %d", &Y, &X);
    for(int y=1; y<=Y ; ++y){
        for(int x=1; x<=X; ++x){
            scanf("%1d", &mine[y][x]);
        }
    }

    //make adjacent list
    for(int y=1; y<=Y; ++y){
        for(int x=1; x<=X; ++x){
            if(mine[y][x] != 0){
                if(y-1 >=1 && y-1<=Y && x>=1 && x<=X){
                    if(mine[y-1][x] != 0){
                        adj[y][x].push_back(make_pair(y-1,x));
                        adj[y-1][x].push_back(make_pair(y,x));
                    }
                }
                if(y+1 >=1 && y+1<=Y && x>=1 && x<=X){
                    if(mine[y+1][x] !=0){
                        adj[y][x].push_back(make_pair(y+1,x));
                        adj[y+1][x].push_back(make_pair(y,x));     
                    }
                }

                if(y >=1 && y<=Y && x-1>=1 && x-1<=X){
                    if(mine[y][x-1] !=0){
                        adj[y][x].push_back(make_pair(y,x-1));
                        adj[y][x-1].push_back(make_pair(y,x));
                    }

                }

                if(y >=1 && y <=Y && x+1>=1 && x+1<=X){
                    if(mine[y][x+1] != 0){
                        adj[y][x].push_back(make_pair(y,x+1));
                        adj[y][x+1].push_back(make_pair(y,x));
                    }

                }
            }
        }
    }

    printf("%d",bfs(1,1));
}
epdlqlemqpzja1234 (2)
Test Min Distance
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
 
#include<iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

int MIN = 10000;
int Y;
int X;
int mine[100+10][100+10];
vector<pair<int, int>> adj[100+10][100+10];

int bfs(int y, int x)
{
    queue<pair<int, int>> que; 
    int visited[100+10][100+10]={0,};

    que.push(make_pair(y,x));
    visited[y][x] = 1;
    
    while(!que.empty()){
        pair<int,int> v = que.front();
        que.pop();
        
        if(v.first == Y && v.second == X){
            if(MIN > visited[v.first][v.second]){
                MIN = visited[v.first][v.second];
            }
        }

        for(size_t i=0; i<adj[v.first][v.second].size(); ++i){
            if(visited[adj[v.first][v.second][i].first][adj[v.first][v.second][i].second] == 0)
                que.push(make_pair(adj[v.first][v.second][i].first, adj[v.first][v.second][i].second));
                visited[adj[v.first][v.second][i].first][adj[v.first][v.second][i].second] = visited[v.first][v.second]+1;
                
        }
    }

    // for(int y=1; y<=Y; ++y){
    //     for(int x=1; x<=X; ++x){
    //         printf("%d ", visited[y][x]);
    //     }
    //     printf("\n");
    // }

    return MIN;
}

int main()
{
    scanf("%d %d", &Y, &X);
    for(int y=1; y<=Y ; ++y){
        for(int x=1; x<=X; ++x){
            scanf("%1d", &mine[y][x]);
        }
    }

    //make adjacent list
    for(int y=1; y<=Y; ++y){
        for(int x=1; x<=X; ++x){
            if(mine[y][x] != 0){
                if(y-1 >=1 && y-1<=Y && x>=1 && x<=X){
                    if(mine[y-1][x] != 0){
                        adj[y][x].push_back(make_pair(y-1,x));
                        adj[y-1][x].push_back(make_pair(y,x));
                    }
                }
                if(y+1 >=1 && y+1<=Y && x>=1 && x<=X){
                    if(mine[y+1][x] !=0){
                        adj[y][x].push_back(make_pair(y+1,x));
                        adj[y+1][x].push_back(make_pair(y,x));     
                    }
                }

                if(y >=1 && y<=Y && x-1>=1 && x-1<=X){
                    if(mine[y][x-1] !=0){
                        adj[y][x].push_back(make_pair(y,x-1));
                        adj[y][x-1].push_back(make_pair(y,x));
                    }

                }

                if(y >=1 && y <=Y && x+1>=1 && x+1<=X){
                    if(mine[y][x+1] != 0){
                        adj[y][x].push_back(make_pair(y,x+1));
                        adj[y][x+1].push_back(make_pair(y,x));
                    }

                }
            }
        }
    }

    printf("%d",bfs(1,1));
}
Topic archived. No new replies allowed.