https://ac.nowcoder.com/acm/contest/330/C

C++版本一

std

題解：

搜索，模擬

BFS 求最短路。
注意點是狀態要三維。d[x][y][0/1]表示在(x, y)處，屬性為水/火的最短路。
按題意模擬，分類討論轉移即可。

#include <bits/stdc++.h> using namespace std;typedef pair<pair<int, int>, int> Node; const int maxn = 105; char maze[maxn][maxn]; int vis[maxn][maxn][2]; int tx[] = {-1, 0, 1, 0}; int ty[] = {0, -1, 0, 1};int bfs(const pair<int, int>& S,const pair<int, int>& T,int n, int m) {memset(vis, -1, sizeof(vis));queue<Node> q;q.push({S, 0});vis[S.first][S.second][0] = 0;while (!q.empty()){Node tmp = q.front();q.pop();int x = tmp.first.first, y = tmp.first.second;bool p = tmp.second;for (int i = 0; i < 4; i++){int nx = x + tx[i], ny = y + ty[i];if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;if (~vis[nx][ny][p]) continue;if (maze[nx][ny] == '#') continue;if (p && maze[nx][ny] == '~') continue;if (!p && maze[nx][ny] == 'w') continue;vis[nx][ny][p] = vis[x][y][p] + 1;pair<int, int> nxt = {nx, ny};if (nxt == T) return vis[nx][ny][p];q.push({nxt, p});}if (maze[x][y] == '@' && vis[x][y][p ^ 1] == -1){vis[x][y][p ^ 1] = vis[x][y][p] + 1;q.push({tmp.first, p ^ 1});}}return -1; }int main() {int n, m;pair<int, int> S, T;scanf("%d%d", &n, &m);for (int i = 0; i < n; i++)scanf("%s", maze[i]);for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)if (maze[i][j] == 'S')S = {i, j};else if (maze[i][j] == 'T')T = {i, j};int ans = bfs(S, T, n, m);printf("%d\n", ans);return 0; }掃一掃，把題目裝進口袋

C++版本二

BFS

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; //typedef __int128 lll; const int N=1000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,sx,sy,ex,ey; int ans,cnt,flag,temp; int dir[][2]={0,1,1,0,0,-1,-1,0}; char str[N][N]; bool vis[N][N][2]; struct node{int x,y,f,step; }s,tmp,f; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifscanf("%d%d",&n,&m);//scanf("%d",&t);//while(t--){}for(int i=1;i<=n;i++){scanf("%s",str[i]+1);for(int j=1;j<=m;j++){if(str[i][j]=='S')sx=i,sy=j;if(str[i][j]=='T')ex=i,ey=j;}}queue<node>q;s.x=sx;s.y=sy;s.f=0;s.step=0;vis[sx][sx][0]=1;q.push(s);while(!q.empty()){f=q.front();q.pop();//cout<<f.x<<" "<<f.y<<endl;if(f.x==ex&&f.y==ey){flag=1;break;}f.step++;tmp=f;if(str[f.x][f.y]=='@'){tmp.f=!tmp.f;if(vis[tmp.x][tmp.y][tmp.f]==0){vis[tmp.x][tmp.y][tmp.f]=1;q.push(tmp);}}tmp=f;for(int i=0;i<4;i++){tmp.x=f.x+dir[i][0];tmp.y=f.y+dir[i][1];if(tmp.x<1||tmp.y<1||tmp.x>n||tmp.y>m)continue;if(str[tmp.x][tmp.y]=='#')continue;if(vis[tmp.x][tmp.y][tmp.f])continue;if(str[tmp.x][tmp.y]=='~'&&tmp.f==1)continue;if(str[tmp.x][tmp.y]=='w'&&tmp.f==0)continue;vis[tmp.x][tmp.y][tmp.f]=1;q.push(tmp);}}if(flag)cout<<f.step<<endl;elsecout<<-1<<endl;//cout << "Hello world!" << endl;return 0; }

?

總結

以上是生活随笔為你收集整理的Applese 走迷宫的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。