本文共 2806 字，大约阅读时间需要 9 分钟。

题意：

 的迷宫，有  个格子是障碍，移动的方向是上下左右。

每个格子只能经过一次。

每个格子在经过时若要变换方向，只能向右变换一次。

问从  出发，能否遍历所有非障碍的格子。

数据范围： ， 。

题解：

走的轨迹大致是一个螺旋形。

在可以直走和拐弯时，选择直走，因为拐弯后不可能走到原来直走的格子上。

用set存储障碍。然后二分障碍的位置就好了。

如果可以完成任务，那么走的路径长度是  。

感受：

在AC之前能不看数据就不看数据。

代码：

#include<bits/stdc++.h>using namespace std ;typedef long long ll ;const int maxn = 1e5 + 5 ;int n , m , k ;set<int> row[maxn] , col[maxn] ;ll s = 0 ;int r , c , d ;int ur , dr , lc , rc ;bool can(){	if(d == 0)  	{	   auto it = row[r].upper_bound(c) ;	   int nxt ;	   if(it == row[r].end())  nxt = m ;	   else  nxt = *it - 1 ;	   nxt = min(nxt , rc - 1) ;	   if(nxt <= c)  return 0 ;	   else  return 1 ;		}	else if(d == 1)	{	   auto it = col[c].upper_bound(r) ;	   int nxt ;	   if(it == col[c].end())  nxt = n ;	   else  nxt = *it - 1 ;	   nxt = min(nxt , dr - 1) ;	   if(nxt <= r)  return 0 ;	   else  return 1 ;		}	else if(d == 2)	{	   auto it = row[r].upper_bound(c) ;	   if(it != row[r].begin())  it -- ;	   int nxt ;	   if(it == row[r].end() || (*it) > c)  nxt = 1 ;	   else  nxt = (*it) + 1 ;	   nxt = max(nxt , lc + 1) ;	   if(nxt >= c)  return 0 ;	   else  return 1 ;		}	else	{	   auto it = col[c].upper_bound(r) ;	   if(it != col[c].begin())  it -- ;	   int nxt ;	   if(it == col[c].end() || (*it) > r)  nxt = 1 ;	   else  nxt = (*it) + 1 ;	   nxt = max(nxt , ur + 1) ;	   if(nxt >= r)  return 0 ;	   else  return 1 ;			}}void work(){	if(d == 0)  	{	   auto it = row[r].upper_bound(c) ;	   int nxt ;	   if(it == row[r].end())  nxt = m ;	   else  nxt = *it - 1 ;	   nxt = min(nxt , rc - 1) ;	   s += nxt - c ;	   c = nxt ;	   rc = min(rc , c) ;	}	else if(d == 1)	{	   auto it = col[c].upper_bound(r) ;	   int nxt ;	   if(it == col[c].end())  nxt = n ;	   else  nxt = *it - 1 ;	   nxt = min(nxt , dr - 1) ;	   s += nxt - r ;	   r = nxt ;	   dr = min(dr , r) ;	}	else if(d == 2)	{	   auto it = row[r].upper_bound(c) ;	   if(it != row[r].begin())  it -- ;	   int nxt ;	   if(it == row[r].end() || (*it) > c)  nxt = 1 ;	   else  nxt = (*it) + 1 ;	   nxt = max(nxt , lc + 1) ;	   s += c - nxt ;	   c = nxt ;	   lc = max(lc , c) ;	}	else	{	   auto it = col[c].upper_bound(r) ;	   if(it != col[c].begin())  it -- ;	   int nxt ;	   if(it == col[c].end() || (*it) > r)  nxt = 1 ;	   else  nxt = (*it) + 1 ;	   nxt = max(nxt , ur + 1) ;	   s += r - nxt ;	   r = nxt ;	   ur = max(ur , r) ;			}}void solve(){    r = 1 , c = 1 , d = 0 ;   ur = 1 , dr = n + 1 , lc = 0 , rc = m + 1 ;   while(1)   {      if(can())  	    work() ;      else 	  {	  	 d = (d + 1) % 4 ;	  	 if(can())  		   work() ;         else  break ;	  }	     }	}int main(){	scanf("%d%d%d" , &n , &m , &k) ;	for(int i = 1 ; i <= k ; i ++)    {    	int r , c ;    	scanf("%d%d" , &r , &c) ;    	row[r].insert(c) ;    	col[c].insert(r) ;	}	solve() ;	if(s == ll(n) * m - k - 1)  printf("Yes\n") ;	else  printf("No\n") ;	return 0 ;}