小红走矩阵
题目描述
小红来到了一个n∗m的矩阵，她初始站在左上角，每次行走可以按“上下左右”中的一个方向走一步，但必须走到和当前格子不同的字符，也不能走到矩阵外。
小红想知道，从左上角走到右下角最少需要走多少步？
输入描述:
第一行输入两个正整数n,m,用空格隔开。代表矩阵的行数和列数。
接下来的nnn行，每行输入一个长度为m的、仅由小写字母组成的字符串，用来表示矩阵。
1≤n,m≤1000
输出描述:
如果无法到达右下角，则输出-1。
否则输出一个整数，代表行走的最小步数。
输入
3 4
abbc
accd
bcee
输出
9
说明
#include<iostream> #include<bits/stdc++.h> using namespace std; int dx[4]={-1,0,1,0}; int dy[4]={0,-1,0,1}; using T=tuple<int,int,int>; const int N=1005; string a[N]; bool b[N][N]; int n,m; int bfs() { queue<T> q; int x,y,z,nx,ny,i; q.emplace(0,0,0); b[0][0]=true; while(!q.empty()) { tie(x,y,z)=q.front(); q.pop(); if(x==n-1&&y==m-1) return z; else { for(i=0;i<4;++i) { nx=x+dx[i]; ny=y+dy[i]; if(0<=nx&&nx<n&&0<=ny&&ny<m&&!b[nx][ny]&&a[x][y]!=a[nx][ny]) { b[nx][ny]=true; q.emplace(nx,ny,z+1); } } } } return -1; } int main(void) { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int i,j; cin>>n>>m; for(i=0;i<n;++i) cin>>a[i]; cout<<bfs(); return 0; }
小红的小红走矩阵
题目描述
小红在出题“小红的走矩阵”时，在数据生成的环节发现了一些问题。
如果直接随机生成一个矩阵，那么结果大概率可以直接输出 n+m−2。
如果直接生成极限数据，那么结果也将是跑完整个矩阵，因此可以直接输出 n∗m−1。
为了避免以上的情况骗到分，于是小红想到了另一个方案：先随机生成一个从 (1,1)( 到 (n,m)的路径，再将路径以外的矩阵的部分全部填成同一个字符。这样一来看似数据确实强，答案并不固定，但实际上也有非常明显的弊端，因为矩阵中大部分都是同一个字符，且这个字符在路径之外，因此选手可以通过“矩阵中是否存在绝对众数”来判断数据是否是这样的数据。
因此小红现在在数据生成的问题上犯了难，她希望小苯帮她来完成本题数据的生成，即请你来代替小苯构造出本题较强的数据。
使得所有的数据都能满足以下的所有条件：
1.1.1. 直接输出 n+m−2n会返回答案错误，换句话说，“小红走矩阵”这题的正确代码运行后的结果不是 n+m−2。
2.2.2. 直接输出 n∗m−1 也会返回答案错误，换句话说，“小红走矩阵”这题的正确代码运行后的结果不是 n∗m−1。
3.3.3. 生成的矩阵中，不存在“绝对众数”。（即，没有任何字符的出现次数大于 n∗m/2 向上取整）
4.4.4. 生成的矩阵必须能从 (1,1)走到 (n,m)，换句话说，“小红走矩阵”这题的正确代码运行后的结果不是 −1。
输入描述:
输入包含一行两个正整数 n,m (3≤n,m≤10^3)，分别表示需要生成的矩阵的大小，以空格分割。
输出描述:
输出包含一个 n 行 m列 的字符矩阵，满足题目所述的要求，且仅由小写英文字母构成。（如果有多种方案，输出任意即可）
输入
3 4
输出
abbc
accd
bcee
说明
路线如图，最短路长度为9，且满足题目的所有条件。
备注:
#include<iostream> #include<string.h> #include<bits/stdc++.h> using namespace std; int main(){ int m, n; cin >> m >> n; cout << "abb" << string(n - 3, 'a') << '\n'; cout << "acc" << string(n - 3, 'b') << '\n'; cout << "bcd" ; for(int i = 3; i < n; i ++) { char s = ('a' + (i + m) % 26); cout << s; } cout <<'\n'; for(int i = 3; i < m - 1; ++i ) { char s= ('a' + i % 26); cout << string(n,s) <<'\n'; } if(m > 3){ for(int i = 0; i < n; i ++) { char s= ('a' + (i + m) % 26); cout << s; } } }
