看大神寫的dp[x][y][c]表示的（x，y）位置c方向的三維DFS，


這題說是轉(zhuǎn)不超過兩個彎，其實就是連連看。
掃描S和T左右上下達到的最大點。
左右上下都取S和T達到的最小范圍。


1.用左右范圍算是否有一條上下通路，如果有則輸出YES
2.用上下范圍算是否有一條左右通路，如果有則輸出YES
3.否則輸出NO。

代碼如下：

#include<bits\stdc++.h> using namespace std; typedef long long ll; char a[1010][1010]; int main(){int n,m;cin >> n >> m;int x1,y1,x2,y2;for(int i = 0;i < n; i++){for(int j = 0;j < m; j++){cin >> a[i][j];if(a[i][j] == 'S') x1 = i,y1 = j;else if(a[i][j] == 'T') x2 = i,y2 = j;}}int mn = 0,mx = m-1;int j = y1;while(j + 1 < m&&a[x1][j+1] != '*'){j++;}mx = min(mx,j);j = y1;while(j - 1 >= 0&&a[x1][j-1] != '*'){j--;}mn = max(mn,j);j = y2;while(j + 1 < m&&a[x2][j+1] != '*'){j++;}mx = min(mx,j);j = y2;while(j - 1 >= 0&&a[x2][j-1] != '*'){j--;}mn = max(mn,j);for(int i = mn;i <= mx; i++){int s = 0;for(int j = min(x1,x2);j <= max(x1,x2); j++){if(a[j][i] == '*') s = 1;}if(s == 0){cout << "YES" << endl;return 0;}}mn = 0,mx = n-1;int i = x1;while(i + 1 < n&&a[i+1][y1] != '*'){i++;}mx = min(mx,i);i = x1;while(i - 1 >= 0&&a[i-1][y1] != '*'){i--;}mn = max(mn,i);i = x2;while(i + 1 < n&&a[i+1][y2] != '*'){i++;}mx = min(mx,i);i = x2;while(i - 1 >= 0&&a[i-1][y2] != '*'){i--;}mn = max(mn,i);for(int i = mn;i <= mx; i++){int s = 0;for(int j = min(y1,y2);j <= max(y1,y2); j++){if(a[i][j] == '*') s = 1;}if(s == 0){cout << "YES" << endl;return 0;}}cout << "NO" << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的Codeforces 793b B. Igor and his way to work 觉得大神写的3维bfs太复杂，突然发现这题是连连看算法。的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。