Codeforces 106 D Treasure Island

题目链接~~>

做题感悟：这题做着很有感觉，从超时一直优化改到AC。

解题思路：

                这题如果不预先处理图的话，单纯的模拟肯定超时，so ~需要预先处理图，因为向 N 和 S 是 y 不变，x 变化，向 W 和 E x 不变 ,变 y . 这样可以用两个 vector 然后分别存x 不变的时候 y 的值，y 不变的时候 x 的值，这样查询的时候直接固定 x ,或者 y 然后找变化的。复杂度为最大为 26 * 1000 * 1000 。

代码：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<cmath>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<bitset>
     
    
   

    

     

    
    

     

      #include<ctime>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std  ;
     
    
   

    

     

    
    

     

      #define INT __int64
     
    
   

    

     

    
    

     

      const int INF = 99999999 ;
     
    
   

    

     

    
    

     

      const double esp = 0.0000000001 ;
     
    
   

    

     

    
    

     

      const double PI = acos(-1.0) ;
     
    
   

    

     

    
    

     

      const int MY = 100000 + 5 ;
     
    
   

    

     

    
    

     

      const int MX = 1000 + 5 ;
     
    
   

    

     

    
    

     

      int n ,m ,num ,Q ,Gnum ;
     
    
   

    

     

    
    

     

      char s[MX][MX] ,s1[50] ;
     
    
   

    

     

    
    

     

      int dx[4] = {-1 ,1 ,0 ,0} ,dy[4] = {0 ,0 ,-1 ,1} ; // N ,S ,W ,E
     
    
   

    

     

    
    

     

      vector<int>Gx[MX] ,Gy[MX] ;
     
    
   

    

     

    
    

     

      struct node // 存景点
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 char ch ;
     
    
   

    

     

    
    

     
 int x ,y ;
     
    
   

    

     

    
    

     

      }T[50] ;
     
    
   

    

     

    
    

     

      struct move // 各条指令
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int dir ,step ;
     
    
   

    

     

    
    

     

      }Move[MY] ;
     
    
   

    

     

    
    

     

      void input()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x ,y ;
     
    
   

    

     

    
    

     

       num = 0 ; // 记录景点个数
     
    
   

    

     

    
    

     

       Gnum = 0 ;// 记录 # 的个数
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < n ; ++i)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%s" ,s[i]) ;
     
    
   

    

     

    
    

     
 for(int j = 0 ;j < m ; ++j)
     
    
   

    

     

    
    

     
 if(s[i][j] >= 'A' && s[i][j] <= 'Z') // 是景点
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       T[num].x = i ;
     
    
   

    

     

    
    

     

       T[num].y = j ;
     
    
   

    

     

    
    

     

       T[num++].ch = s[i][j] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(s[i][j] == '#') // 是墙
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       Gx[i].push_back(j) ;
     
    
   

    

     

    
    

     

       Gy[j].push_back(i) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 scanf("%d" ,&Q) ;
     
    
   

    

     

    
    

     
 char ch ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < Q ; ++i) // 输入指令
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 cin>>ch>>x ;
     
    
   

    

     

    
    

     
 if(ch == 'N')
     
    
   

    

     

    
    

     

       y = 0 ;
     
    
   

    

     

    
    

     
 else if(ch == 'S')
     
    
   

    

     

    
    

     

       y = 1 ;
     
    
   

    

     

    
    

     
 else if(ch == 'W')
     
    
   

    

     

    
    

     

       y = 2 ;
     
    
   

    

     

    
    

     
 else y = 3 ;
     
    
   

    

     

    
    

     

       Move[i].dir = y ; // 记录指令
     
    
   

    

     

    
    

     

       Move[i].step = x ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      bool solve(int x ,int y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int sx ,sy ,dir ,step ,mt ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < Q ; ++i) // 一次执行 Q 条指令
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       dir = Move[i].dir ;
     
    
   

    

     

    
    

     

       step = Move[i].step ;
     
    
   

    

     

    
    

     
 if(!dir) // N y 不变 上
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sx = x + dx[dir]*step ;
     
    
   

    

     

    
    

     

       mt = Gy[y].size() ;
     
    
   

    

     

    
    

     
 if(sx < 0 || sx >= n)  return false ; // 出界
     
    
   

    

     

    
    

     
 for(int j = 0 ;j < mt ; ++j)
     
    
   

    

     

    
    

     
 if(Gy[y][j] >= sx && Gy[y][j] < x)
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     

       x = sx ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(dir == 1) // S 下 y 不变
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sx = x + dx[dir]*step ;
     
    
   

    

     

    
    

     

       mt = Gy[y].size() ;
     
    
   

    

     

    
    

     
 if(sx < 0 || sx >= n)  return false ; // 出界
     
    
   

    

     

    
    

     
 for(int j = 0 ;j < mt ; ++j)
     
    
   

    

     

    
    

     
 if(Gy[y][j] > x && Gy[y][j] <= sx)
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     

       x = sx ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(dir == 2) // W 左 x 不变
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sy = y + dy[dir]*step ;
     
    
   

    

     

    
    

     

       mt = Gx[x].size() ;
     
    
   

    

     

    
    

     
 if(sy < 0 || sy >= m)  return false ;
     
    
   

    

     

    
    

     
 for(int j= 0 ;j < mt ; ++j)
     
    
   

    

     

    
    

     
 if(Gx[x][j] < y && Gx[x][j] >= sy)
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     

       y = sy ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else  // E 右 x 不变
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sy = y + dy[dir]*step ;
     
    
   

    

     

    
    

     

       mt = Gx[x].size() ;
     
    
   

    

     

    
    

     
 if(sy < 0 || sy >= m)  return false ;
     
    
   

    

     

    
    

     
 for(int j= 0 ;j < mt ; ++j)
     
    
   

    

     

    
    

     
 if(Gx[x][j] > y && Gx[x][j] <= sy)
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     

       y = sy ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return true ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 while(~scanf("%d%d" ,&n ,&m))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       input() ;
     
    
   

    

     

    
    

     
 int nx = 0 ;
     
    
   

    

     

    
    

     
 bool flag = false ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < num ; ++i)
     
    
   

    

     

    
    

     
 if(solve(T[i].x ,T[i].y)) // 判断此起点是否合法
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       flag = true ;
     
    
   

    

     

    
    

     

       s1[nx++] = T[i].ch ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(flag)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       s1[nx] = '\0' ;
     
    
   

    

     

    
    

     

       stable_sort(s1 ,s1+nx) ;
     
    
   

    

     

    
    

     
 cout<<s1<<endl ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else   cout<<"no solution"<<endl ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < Gnum ; ++i)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       Gx[i].clear() ;
     
    
   

    

     

    
    

     

       Gy[i].clear() ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/39578711