URAL 1920 Titan Ruins: the Infinite Power of Magic-白红宇

URAL 1920 Titan Ruins: the Infinite Power of Magic

阅读量：5275 次

发布时间：2019-06-14

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

大意：

有一张N*N的网格，你每次可以走一步，每格只能走一次，有没有一种方法让走了L步后回到一个距原点1步远的格子？

没有输出Unsuitable device，否则输出Overwhelming power of magic并输出方案。

一开始用DFS 奇偶剪枝了还是TLE,

代码如下：

#include
       
        #include
        
         #include
         
          #define N 110using namespace std;int n,t,end_i,end_j;bool visited[N][N],flag,ans;char map[N][N];int run[10010][2];int tem;int a[4][2]={
      {-1,0},{1,0},{0,-1},{0,1}};void DFS(int i,int j,int c){if(flag){ return ;}    if(c>t) return ;    if(i<=0||i>n||j<=0||j>n) {return ;}    if(map[i][j]=='D'&&c==t) {flag=ans=true; return ;}    int temp=abs(i-end_i)+abs(j-end_j);    temp=t-temp-c;         //t扣掉还要走的最短步temp 和 已经走过的 c 如果这些步还是奇数直接不满足    if(temp&1) return ;//奇偶剪枝 奇数return   for(int k=0;k<4;k++)    	if(!visited[i+a[k][0]][j+a[k][1]]) //开始进行各个方向的探索 记得回溯，取消之前走的状态    	{    	 visited[i+a[k][0]][j+a[k][1]]=true;    	 DFS(i+a[k][0],j+a[k][1],c+1);    	 if(flag){cout<
          
           <<" "<
           
            <
            
             >n>>t) { if(t%2!=0||t>n*n){cout<<"Unsuitable device"<

后来是找规律做出来的，根据奇偶分类讨论一下；；

代码写的很烂。。

很多复用的没复用。。

#include
       
        #include
        
         #include
         
          #define N 110using namespace std;int n,t,end_i,end_j;bool visited[N][N],flag,ans;char map[N][N];int run[10010][2];int tem;int a[4][2]={
      {-1,0},{1,0},{0,-1},{0,1}};int main(){    int i;int xx,yy,kk;    while(cin>>n>>t)    {    	if(t%2!=0||t>n*n){cout<<"Unsuitable device"<
          
           0;i--){    			    				cout<<2<<" "<
           <
            
             =2;i--){ cout<
             <<" "<
              
               <
               
                =2;i--) cout<
                <<" "<
                 
                  <
                  
                   =2;i--) cout<
                   <<" "<
                    
                     <
                     
                      0;i--){ cout<<2<<" "<
                      <
                       
                        =3;i--){ cout<<2<<" "<
                        <
                         
                          =2;i--){ cout<
                          <<" "<<1<
                           
                            =3;i--){ cout<<2<<" "<
                            <
                             
                              0&&y==1&&x%2==0){ y=2;bb--; cout<
                              
                               <<" "<
                               
                                <
                                
                                 =2;i--){ cout<
                                 <<" "<
                                  
                                   <
                                   
                                    =2;i--) cout<
                                    <<" "<
                                     
                                      <
                                      
                                       =2;i--) cout<
                                       <<" "<
                                        
                                         <

有的队也有用DFS过的T T

#include
       
        using namespace std;int n,l,ans;void dfs(int x,int y,int z){	if(ans==l) return ;	if(x>n||y>n) return ;	if(z==0){		printf("%d %d\n",x,y);		ans+=2;		dfs(x+1,y,0);		printf("%d %d\n",x,y+1);		if(n%2==x%2) dfs(x,3,1);	}	else if(z==1){		printf("%d %d\n",x,y);		ans+=2;		dfs(x,y+1,1);		printf("%d %d\n",x-1,y);		if(x==3&&y%2==0) dfs(x-2,y,2);	}	else if(z==2){		ans+=2;		printf("%d %d\n",x,y);		printf("%d %d\n",x,y-1);	}}int main(){	cin>>n>>l;	if(l%2==1||n*n