Treasure Island（两遍dfs）-- Codeforces Round #583 (Div. 1 + Div. 2, based on Olympiad of Metropolises)

  1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);
  2 #include <cstdio>//sprintf islower isupper
  3 #include <cstdlib>//malloc  exit strcat itoa system("cls")
  4 #include <iostream>//pair
  5 #include <fstream>//freopen("C:\\Users\\13606\\Desktop\\草稿.txt","r",stdin);
  6 #include <bitset>
  7 #include <map>
  8 //#include<unordered_map>
  9 #include <vector>
 10 #include <stack>
 11 #include <set>
 12 #include <string.h>//strstr substr
 13 #include <string>
 14 #include <time.h>//srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
 15 #include <cmath>
 16 #include <deque>
 17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less
 18 #include <vector>//emplace_back
 19 //#include <math.h>
 20 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor
 21 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)
 22 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
 23 #define fo(a,b,c) for(register int a=b;a<=c;++a)
 24 #define fr(a,b,c) for(register int a=b;a>=c;--a)
 25 #define mem(a,b) memset(a,b,sizeof(a))
 26 #define pr printf
 27 #define sc scanf
 28 #define ls rt<<1
 29 #define rs rt<<1|1
 30 typedef long long ll;
 31 void swapp(int &a,int &b);
 32 double fabss(double a);
 33 int maxx(int a,int b);
 34 int minn(int a,int b);
 35 int Del_bit_1(int n);
 36 int lowbit(int n);
 37 int abss(int a);
 38 //const long long INF=(1LL<<60);
 39 const double E=2.718281828;
 40 const double PI=acos(-1.0);
 41 const int inf=(1<<30);
 42 const double ESP=1e-9;
 43 const int mod=(int)1e9+7;
 44 const int N=(int)1e6+10;
 45 
 46 int n,m,tot=0;
 47 vector<vector<char> >v(N);
 48 map<int,int>mp[N];
 49 map<int,int>mp2[N],vis[N],vis2[N];
 50 struct node
 51 {
 52     int x,y;
 53 };
 54 bool f1,f2;
 55 void dfs1(int x,int y)
 56 {
 57     if(x==n&&y==m)
 58         f1=1,vis[x][y]=1;
 59     if(f1||vis[x][y]||x>n||y>m)return;
 60     vis[x][y]=1;
 61     //pr("%d %d\n",x,y);
 62     if(x+1<=n&&v[x+1][y]==‘.‘)
 63         dfs1(x+1,y);
 64     if(y+1<=m&&v[x][y+1]==‘.‘)
 65         dfs1(x,y+1);
 66 }
 67 
 68 void dfs2(int x,int y)
 69 {
 70     if(x==n&&y==m)
 71         f2=1,vis2[x][y]=1;
 72     if(f2||vis2[x][y]||x>n||y>m)return;
 73     vis2[x][y]=1;
 74 //    pr("%d %d\n",x,y);
 75     if(y+1<=m&&v[x][y+1]==‘.‘)
 76         dfs2(x,y+1);
 77     if(x+1<=n&&v[x+1][y]==‘.‘)
 78         dfs2(x+1,y);
 79 }
 80 
 81 
 82 int main()
 83 {
 84     sc("%d%d",&n,&m);
 85     for(int i=1;i<=n;++i)
 86         v[i].push_back(‘$‘);
 87     for(int i=1;i<=n;++i)
 88     {
 89         for(int j=1;j<=m;++j)
 90         {
 91             char s[5];
 92             sc("%1s",s);
 93             v[i].push_back(s[0]);
 94         }
 95     }
 96     dfs1(1,1);
 97     dfs2(1,1);
 98     bool F=0;
 99     for(int i=1;i<=n;++i)
100     {
101         for(int j=1;j<=m;++j)
102         {
103             if(i==1&&j==1||i==n&&j==m)
104                 continue;
105             if(vis[i][j]&&vis2[i][j])
106                 F=1;
107         }
108     }
109     if(vis[n][m]!=1)
110         pr("0\n");
111     else
112     {
113         if(F)
114             pr("1\n");
115         else
116             pr("2\n");
117     }
118     return 0;
119 }
120 
121 /**************************************************************************************/
122 
123 int maxx(int a,int b)
124 {
125     return a>b?a:b;
126 }
127 
128 void swapp(int &a,int &b)
129 {
130     a^=b^=a^=b;
131 }
132 
133 int lowbit(int n)
134 {
135     return n&(-n);
136 }
137 
138 int Del_bit_1(int n)
139 {
140     return n&(n-1);
141 }
142 
143 int abss(int a)
144 {
145     return a>0?a:-a;
146 }
147 
148 double fabss(double a)
149 {
150     return a>0?a:-a;
151 }
152 
153 int minn(int a,int b)
154 {
155     return a<b?a:b;
156 }