真是发现个有趣(奔溃)的现象。我们来看以下三种题解代码(注明:参考代码。来源于CSDN和本题的解析) 先看第一类
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int A[30][30],x,y,z,w;
char s1[10],s2[10];
int a,b,op,n;
void Find(int c,int &u,int &v){
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(A[i][j]==c){ u=i;v=j;}
}
bool islegal(){
if(a==b)return 0;
Find(a,x,y);
Find(b,z,w);
if(x==z)return 0;
return 1;
}
void restore(int p){
Find(p,x,y);
while(A[x][++y]!=-1){
int t= A[x][y];
A[t][0]=t;
A[x][y]=-1;
}
}
void pile(int a,int b){
Find(a,x,y);
Find(b,z,w);
while(A[z][++w]!=-1);w--;
while(A[x][y]!=-1){
A[z][++w]=A[x][y];
A[x][y++]=-1;
}
}
int main(){
//freopen("1.in","r",stdin);
scanf("%d",&n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)A[i][j]=-1;
A[i][0]=i;
}
while(scanf("%s",s1)!=EOF && s1[0]!='q'){
scanf("%d%s%d",&a,s2,&b);
if(islegal()==0)continue;
if(s1[0]=='m')restore(a);
if(s2[1]=='n')restore(b);
pile(a,b);
}
for(int i=0;i<n;i++){
printf("%d:",i);
int k=0;
while(A[i][k]!=-1)
printf(" %d",A[i][k++]);
printf("\n");
}
}
这段来源于解析,当我们测试同一个测试用例时,如下 7
move 6 over 5
pile 3 on 0
pile 5 on 1
move 2 on 0
pile 0 on 1
move 0 over 2
move 1 over 1
move 5 over 3
pile 6 over 5
pile 3 over 1
quit 此时的答案是 0: 1: 1 3 5 6 2: 2 0 3: 4: 4 5: 6: 代码可以AC通过
再看下面第二类代码
#include<cstdio>
#include<string>
#include<vector>
#include<iostream>
using namespace std;
const int maxn = 30;
int n;
vector<int> pile[maxn];
//找木块a所在的pile 和height, 以引用的形式返回调用者
void find_block(int a , int & p , int & h)
{
for(p = 0 ; p < n ;p++)
for( h = 0 ; h < pile[p].size() ; h++)
if(pile[p][h]==a) return;
}
//把第p堆高度为h的木块上方的所有木块移回原位
void clear_above(int p , int h )
{
for(int i = h+1; i < pile[p].size(); i++)
{
int b = pile[p][i];
pile[b].push_back(b);//把木块b放回原位
}
pile[p].resize(h+1);//pile只保留下标为0~h的元素
}
//把第p堆高度为h及其上方的木块整体移动到p2堆的顶部
void pile_onto(int p , int h , int p2)
{
for(int i = h ; i < pile[p].size() ; i++)
pile[p2].push_back(pile[p][i]);
pile[p].resize(h);
}
void print()
{
for(int i = 0 ; i < n ;i++)
{
printf("%d:",i);
for(int j = 0 ;j < pile[i].size();j++) printf(" %d",pile[i][j]);
printf("\n");
}
}
int main()
{
int a , b;
cin>>n;
string s1 , s2;
for(int i = 0 ; i < n ;i++) pile[i].push_back(i);
while(cin>>s1>>a>>s2>>b)
{
int pa , pb , ha, hb ;
find_block(a,pa,ha);
find_block(b,pb,hb);
if(pa==pb) continue;//非法指令
if(s2=="onto") clear_above(pb,hb);
if(s1=="move") clear_above(pa,ha);
pile_onto(pa,ha,pb);
}
print();
return 0;
}
此时输入同上的示例,答案是 0: 1: 1 5 6 0 3 2 2: 3: 4: 4 5: 6:
在看第三类代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int A[30][30],x,y,z,w;
char s1[10],s2[10];
int a,b,op,n;
void Find(int c,int &u,int &v){
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(A[i][j]==c){ u=i;v=j;}
}
bool islegal(){
if(a==b)return 0;
Find(a,x,y);
Find(b,z,w);
if(x==z)return 0;
return 1;
}
void restore(int p){
Find(p,x,y);
while(A[x][++y]!=-1){
int t= A[x][y];
A[t][0]=t;
A[x][y]=-1;
}
}
void pile(int a,int b){
Find(a,x,y);
Find(b,z,w);
while(A[z][++w]!=-1);w--;
while(A[x][y]!=-1){
A[z][++w]=A[x][y];
A[x][y++]=-1;
}
}
int main(){
//freopen("1.in","r",stdin);
scanf("%d",&n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)A[i][j]=-1;
A[i][0]=i;
}
while(scanf("%s",s1)!=EOF && s1[0]!='q'){
scanf("%d%s%d",&a,s2,&b);
if(islegal()==0)continue;
if(s1[0]=='m')restore(a);
if(s2[1]=='n')restore(b);
pile(a,b);
}
for(int i=0;i<n;i++){
printf("%d:",i);
int k=0;
while(A[i][k]!=-1)
printf(" %d",A[i][k++]);
printf("\n");
}
}
同样是AC,此时输入同第一个的示例,答案却是 0: 1: 1 0 2 3 5 6 2: 3: 4: 4 5: 6:
我就很奔溃,为什么会这样呢? 最后我附上我的通不过的代码
#include <iostream>
#include <vector>
#include <iomanip>
#include <string>
#include <sstream>
#include <stack>
#include <utility>
using namespace std;
//输出vector
/* 不Accept
std::ostream& operator<<(std::ostream& out, vector<vector<int> >& vect) //为vector重载<<运算符
{
int i = 0;
for (vector<vector<int> >::iterator iter = vect.begin(); iter != vect.end(); iter++) //通过迭代器遍历所有元素,等价于for_each()
{
out << i << ":";
for (int i = 0; i < iter->size(); i++) {
out <<" "<<(*iter)[i];
}
i++;
out << endl;
}
return out;
}
*/
void print(vector<vector<int> >& vect) {
int i = 0;
for (vector<vector<int> >::iterator iter = vect.begin(); iter != vect.end(); iter++) //通过迭代器遍历所有元素,等价于for_each()
{
cout << i << ":";
for (int i = 0; i < iter->size(); i++) {
cout << " " << (*iter)[i];
}
i++;
cout << endl;
}
}
//物理模型地址模拟方法
pair<int, int> search(vector<vector<int> >& vect, int number) { //寻找该数所在的坐标(列,高)
for (int i = 0; i < vect.size(); i++) {
for (int j = 0; j < vect[i].size(); j++) {
if (vect[i][j] == number) {
return make_pair(i, j);
}
}
}
}
//---------------vector个数守恒原则:push_back()和pop_back()对应。
void reset(vector<vector<int> >& vect, int x, int y) { //复位(x,y)位置之上的木块
int number;
if (vect[x].size() >= y + 1) {
for (int i = 0; i < vect[x].size() - y - 1; /*i++*/) { //-y-1不包括本身,-y包括本身。
number = vect[x].back();
vect[number].push_back(number);
vect[x].pop_back();
}
}
}
stack<int> preserve(vector<vector<int> >& vect, int x, int y) { //暂存(x,y)位置之上的木块
stack<int> st;
int number;
if (vect[x].size() >= y + 1) {
for (int i = 0; i < vect[x].size() - y; /*i++*/) { //暂存于堆栈,每执行一次vect[x].size()的大小会减1。
number = vect[x].back();
st.push(number);
vect[x].pop_back();
}
}
return st;
}
void moveonto(vector<vector<int> >& vect, int a, int b) {
int x1, x2, y1, y2;
pair<int, int> p;
p = search(vect, a);
x1 = p.first;
y1 = p.second;
p = search(vect, b);
x2 = p.first;
y2 = p.second;
reset(vect, x1, y1); //a的上方归位
reset(vect, x2, y2); //b的上方归位
vect[x2].push_back(vect[x1][y1]);
vect[x1].pop_back();
}
void moveover(vector<vector<int> >& vect, int a, int b) {
int x1, x2, y1, y2;
pair<int, int> p;
p = search(vect, a);
x1 = p.first;
y1 = p.second;
p = search(vect, b);
x2 = p.first;
y2 = p.second;
reset(vect, x1, y1); //a的上方归位
vect[x2].push_back(vect[x1][y1]);
vect[x1].pop_back();
}
void pileonto(vector<vector<int> >& vect, int a, int b) {
int x1, x2, y1, y2;
pair<int, int> p;
p = search(vect, a);
x1 = p.first;
y1 = p.second;
p = search(vect, b);
x2 = p.first;
y2 = p.second;
reset(vect, x2, y2); //b的上方归位
stack<int> st = preserve(vect, x1, y1);
cout<<st.empty()<<endl;
while (!st.empty()) {
vect[x2].push_back(st.top());
st.pop();
}
//vect[x2].push_back(vect[x1][y1]);
//vect[x1].pop_back();
//vect[x1][y1] = -1;
}
void pileover(vector<vector<int> >& vect, int a, int b) {
int x1, x2, y1, y2;
pair<int, int> p;
p = search(vect, a);
x1 = p.first;
y1 = p.second;
p = search(vect, b);
x2 = p.first;
y2 = p.second;
stack<int> st = preserve(vect, x1, y1);
while (!st.empty()) {
vect[x2].push_back(st.top());
st.pop();
}
//vect[x2].push_back(vect[x1][y1]);
//vect[x1].pop_back();
//vect[x1][y1] = -1;
}
int main() {
///步骤0 竞赛去除stdio的同步
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
///步骤1 输入初始信息
vector<vector<int> > vect;
int N;
cin >> N;
for (int i = 0; i < N; i++) {
vect.push_back(vector<int>(1,i)); //空构造函数用于构建空vector;constructor(分配元素数,元素的值)
}
//cout << vect << endl; //测试代码
///步骤2 操作木块
//string command, buffer;
//stringstream sstream;
//int number;
/// cin.get()每次读取一整行并把由Enter键生成的换行符留在输入队列中,然而cin.getline()每次读取一整行并把由Enter键生成的换行符抛弃。
/// 这里主要针对与char类型
/// getline()则主要针对string类库
//cin.ignore(); //类似于cin.get(),可以忽略cin流里的回车符
/*
getline(cin, command, '\x1A'); //ctrl + z 结束输入
//cout << command;
//利用stringstream流处理字符段
sstream << command;
*/
string action, result;
int start, end;
while (!cin.eof()) { //C语言用 scanf(...) != EOF 或者 ~scanf(...)实现多次数据输入的循环判断检查。
//cin则是!cin.eof()返回流结束位,即按键 ctrl+z 键
//注意:如果a和b已经在一堆中就不要操作,此时认为不用移动,否则会WA。
/* 答案对,但是没法Accept
getline(cin,command);
sstream << command;
sstream >> action;
if (action.compare("quit") == 0) {
break;
}
sstream >> start;
sstream >> result;
sstream >> end;
sstream.clear();
*/
cin >> action;
if (action.compare("quit") == 0) {
break;
}
cin >> start >> result >> end;
pair<int,int> same;
same.first = search(vect, start).first;
same.second = search(vect, end).first;
if (same.first == same.second) //如果木块编号一样则不操作
{
//cout << "此处为同一摞" << endl;
continue;
}
else if (action.compare("move") == 0 && result.compare("onto") == 0) {
if(start < N && end < N && start >= 0 && end >= 0) //用精确的vector则必须限定好取值范围
moveonto(vect, start, end);
}
else if (action.compare("move") == 0 && result.compare("over") == 0) {
if (start < N && end < N && start >= 0 && end >= 0)
moveover(vect, start, end);
}
else if (action.compare("pile") == 0 && result.compare("onto") == 0) {
if (start < N && end < N && start >= 0 && end >= 0)
pileonto(vect, start, end);
}
else if (action.compare("pile") == 0 && result.compare("over") == 0) {
if (start < N && end < N && start >= 0 && end >= 0)
pileover(vect, start, end);
}
}
//cout << vect << endl; //输出结果
print(vect);
return 0;
}
答案是 0: 1: 1 3 5 6 2: 2 0 3: 4: 4 5: 6: 但就是通不过。不知道为什么