Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

坑有點多

Posted by KatrineYang at 2016-09-13 12:38:23 on Problem 1307
用栈记氯经过的位置。得到一个序列之后,记氯每个方格最早和最晚出现的位置。然后遍历的时猴,从最早跳到最晚的位置的后面一个位置。中间的位置對应的方格全都填兖星號
#include <iostream>
#include <stdio.h>
#include <stack>
using namespace std;

int x,y,sX,sY,gX,gY;
int firstV[15][15];
int lastV[15][15];
bool hengW[15][15];
bool zongW[15][15];
int num;
int xSeq[2000], ySeq[2000];

void print(int n){
	if(n==0) printf("???");
	else if(n==-1) printf("   ");
	else if(n<10) printf("  %d", n);
	else if(n<100) printf(" %d", n);
	else printf("%d", n);
}

int main() {
	int cntt = 0;
	while(1){
		cin >> x >> y >> sX >> sY >> gX >> gY;
		if(x+y<=0) break;
		cntt++;
		printf("Maze %d\n\n", cntt);
		for(int i = 1; i <= x; i++){
			for(int j = 1; j <= y; j++){
				firstV[i][j] = -1;
				lastV[i][j] = -1;
			}
		}
		for(int i = 0; i < 15; i++){
			for(int j = 0; j < 15; j++){
				if(i == 0 || i == x) hengW[i][j] = 1;
				else hengW[i][j] = 0;
				if(j == 0 || j == y) zongW[i][j] = 1;
				else zongW[i][j] = 0;
			}
		}
		for(int i = 1; i <= x; i++){
			for(int j = 1; j <= y; j++){
				int temp;
				cin >> temp;
				if(temp&1) zongW[i][j] = 1;
				if(temp&2) hengW[i][j] = 1;
			}
		}
		num = 1;
		int curX = sX, curY = sY;
		int nextX, nextY;
		bool houtui = 0;
		stack<int> xs, ys;
		while(1){
			//cout << curX << " " << curY << endl;
			xSeq[num] = curX, ySeq[num] = curY;
			if(firstV[curX][curY] == -1) firstV[curX][curY] = num;
			lastV[curX][curY] = num;
			xSeq[num] = curX, ySeq[num] = curY;
			if(!houtui){
				xs.push(curX), ys.push(curY);
			}
			if(curX == gX && curY == gY) break;
			num++;
			if(!zongW[curX][curY-1] && firstV[curX][curY-1] == -1){
				nextX = curX, nextY = curY-1;
				houtui = 0;
			}
			else if(!hengW[curX-1][curY] && firstV[curX-1][curY] == -1){
				nextX = curX-1, nextY = curY;
				houtui = 0;
			}
			else if(!zongW[curX][curY] && firstV[curX][curY+1] == -1){
				nextX = curX, nextY = curY+1;
				houtui = 0;
			}
			else if(!hengW[curX][curY] && firstV[curX+1][curY] == -1){
				nextX = curX+1, nextY = curY;
				houtui = 0;
			}
			else{
				houtui = 1;
				//cout << 1 << endl;
				//nextX = lastX, nextY = lastY;
				//cout << xs.size() << endl;
				xs.pop(), ys.pop();
				nextX = xs.top(), nextY = ys.top();
			}
			//lastX = curX, lastY = curY;
			curX = nextX, curY = nextY;
		}
		/*
		for(int i = 1; i <= num; i++){
			cout << xSeq[i] << " " << ySeq[i] << endl;
		}*/
		int state[15][15];
		for(int i = 0; i < 15; i++){
			for(int j = 0; j < 15; j++){
				state[i][j] = -1;
			}
		}
		int numbering = 1;
		int ii = 1;
		while(1){
			int nx = lastV[xSeq[ii]][ySeq[ii]];
			state[xSeq[ii]][ySeq[ii]] = numbering;
			numbering++;
			if(xSeq[ii]==gX && ySeq[ii]==gY) break;
			for(int j = ii+1; j < nx; j++){
				state[xSeq[j]][ySeq[j]] = 0;
			}
			ii = nx+1;
		}
		printf("+");
		for(int i = 0; i < y; i++) printf("---+");
		printf("\n");
		for(int i = 1; i <= x; i++){
			printf("|");
			for(int j = 1; j <= y; j++){
				print(state[i][j]);
				if(zongW[i][j]) printf("|");
				else printf(" ");
			}
			printf("\n+");
			for(int j = 1; j <= y; j++){
				if(hengW[i][j]) printf("---");
				else printf("   ");
				printf("+");
			}
			printf("\n");
		}
		printf("\n\n");
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator