求证无解
  • 板块学术版
  • 楼主Lovely_Elaina
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/3/12 14:35
  • 上次更新2023/10/23 21:46:29
查看原帖
求证无解
781159
Lovely_Elaina楼主2023/3/12 14:35

什么情况会无解(

我觉得一定有解,但事实证明我错了

2n,m1002\le n,m\le 100

下面是我的代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 105;

const int tx[5] = {0,-1,1,-1,1};
const int ty[5] = {0,1,1,-1,-1};

int n,m,cnt;
long long sum=1;
int a[N][N];
bool b = false;

/*
1 右上
2 右下
3 左上
4 左下
*/


int corner(int x,int y){
    if(x == 1 && y == m) return 1;
    if(x == n && y == m) return 2;
    if(x == 1 && y == 1) return 3;
    if(x == n && y == 1) return 4;
    return 0;
}

inline void dfs(int x,int y,int d){
    //cout << x << " " << y << " " << d << endl;

    sum++;
    a[x][y] = sum;
    int p = corner(x,y);
    if(p){
        cnt++;
        if(cnt == 2) return;
        b = true;
        if(p == 1) dfs(x,y-1,4);
        else if(p == 2) dfs(x,y-1,3);
        else if(p == 3) dfs(x,y+1,2);
        else if(p == 4) dfs(x,y+1,1);
        return ;
    }

    if(x == 1 || y == 1 || x == n || y == m){
        /*if(d == 1) dfs(x+1,y+1,2);
        else if(d == 2) dfs(x+1,y+1,1);
        else if(d == 3) dfs(x+1,y-1,4);
        else if(d == 4) dfs(x-1,y-1,3);*/
        if(x == 1){
            if(d == 1){
                dfs(x+1,y+1,2);
                return ;
            }
            else if(d == 3){
                dfs(x+1,y-1,4);
                return ;
            }
        }else if(y == 1){
            if(d == 3){
                dfs(x+1,y-1,1);
                return ;
            }
            else if(d == 4){
                dfs(x+1,y+1,2);
                return ;
            }
        }else if(x == n){
            if(d == 2){
                dfs(x+1,y+1,1);
                return ;
            }
            else if(d == 4){
                dfs(x-1,y-1,3);
                return ;
            }
        }else if(y == m){
            if(d == 2){
                dfs(x+1,y-1,4);
                return ;
            }
            else if(d == 1){
                dfs(x-1,y-1,3);
                return ;
            }
        }
        
    }

    int fx = x + tx[d];
    int fy = y + ty[d];

    dfs(fx,fy,d);


    /*cout << x << " " << y << " " << d << endl;
        cout << fx << " " << fy << " " << d << endl;
        cout << "--------" << endl;

        if(1 <= fx && fx <= n && 1 <= fy && fy <= m){
            dfs(fx,fy,d);
            return ;
        }

        if(d == 1) dfs(fx,fy,2);
        else if(d == 2) dfs(fx,fy,1);
        else if(d == 3) dfs(fx,fy,4);
        else if(d == 4) dfs(fx,fy,3);*/
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n >> m;

    a[n][1] = 1;
    dfs(n-1,2,1);

    cout << sum << endl;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cout << a[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}
2023/3/12 14:35
加载中...